Panda 有一棵拥有 $n$ 个节点的有根树，其中节点 1 是根节点。树中的每个节点 $i$ 都有两个标记：$a_i$ 和 $b_i$。其中一些值被指定为通配符，用 0 表示。具体来说，如果 $x = y$ 或者其中至少有一个是通配符 0，则认为两个值 $x$ 和 $y$ 相等。

对于节点 $i$，令 $T_i$ 表示以节点 $i$ 为根的子树，它由节点 $i$ 本身及其在树中的所有后代组成。对于从 1 到 $n$ 的每个节点 $i$，Panda 会向你提出以下问题，你必须独立回答每一个问题：

• 你可以进行任意次数的交换操作（包括零次）。在每次操作中，你可以选择子树 $T_i$ 内的任意两个节点 $u$ 和 $v$，并交换 $a_u$ 和 $a_v$。判断是否可以通过某种交换序列，使得子树 $T_i$ 中的所有节点 $k$ 都满足 $a_k$ 与 $b_k$ 相等。

请注意，每个询问都是独立的。你所考虑的交换仅针对该特定询问，不会影响后续询问中树的初始状态。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2 \times 10^5$)，表示测试数据的组数。

对于每组测试数据：

第一行包含一个正整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示节点的数量。

第二行包含 $n$ 个整数，其中第 $i$ 个整数为 $a_i$ ($0 \le a_i \le n$)。如果 $a_i = 0$，则表示一个通配符。

第三行包含 $n$ 个整数，其中第 $i$ 个整数为 $b_i$ ($0 \le b_i \le n$)。如果 $b_i = 0$，则表示一个通配符。

接下来的 $n - 1$ 行描述树的结构。每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \ne v$)，表示节点 $u$ 和节点 $v$ 之间的一条边。保证给定的 $n-1$ 条边构成一棵树。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每组测试数据，你必须输出一行，包含一个长度为 $n$ 的二进制字符串 $s$。如果子树 $T_i$ 存在合法的交换方案，则字符串的第 $i$ 个字符 $s_i$ 应为 1，否则为 0。

样例

输入样例 1

3
6
1 5 0 3 4 0
0 3 4 5 2 0
1 2
2 3
2 4
1 5
5 6
5
2 2 3 0 4
4 1 4 2 0
1 2
2 3
3 4
4 5
3
1 2 3
3 2 1
1 2
2 3

输出样例 1

111011
01111
100