钥匙迷宫

Problem Description

有一个有 $2n$ 个节点的树。每个节点拥有一个钥匙或一个锁。钥匙和锁各有 $n$ 种，编号为 $1$ 到 $n$。保证每种钥匙和每种锁均在树上刚好出现一次。 cats 可以选择一个拥有钥匙的节点出发，沿着树的边移动任意多次。cats 每次到达一个拥有钥匙的节点时（包括出发的节点），cats 可以收集这个节点的钥匙。只有当 cats 拥有编号为 $i$ 的钥匙时，cats 才可以移动到拥有编号为 $i$ 的锁的节点。钥匙是不会被消耗的，也就是 cats 在获得编号为 $i$ 的钥匙后，他可以移动到拥有编号为 $i$ 的锁的节点任意多次。 现在 cats 想知道，对于每个拥有钥匙的节点，如果他选择这个节点作为出发的节点，他能否收集到全部的 $n$ 种钥匙。你能告诉 cats 答案吗？

Input

第一行包含一个整数 $T$ （$1\leq T \leq 2\cdot 10^4$），表示一共有 $T$ 组测试数据。 对于每组测试数据： 第一行为一个整数 $n$ （$1\leq n\leq 2\cdot 10^5$），表示钥匙的总数和锁的总数。 第二行为 $2n$ 个整数 $a_1,a_2,\dots a_{2n}$ （$-n \leq a_i \leq n,a_i \neq 0$），表示每个节点拥有的钥匙或锁的编号。其中 $a_i > 0$ 表示这个节点拥有编号为 $a_i$ 的钥匙，$a_i < 0$ 表示这个节点拥有编号为 $-a_i$ 的锁。保证每种钥匙和每种锁均在树上刚好出现一次。 接下来 $2n - 1$ 行，每行两个整数 $u_i,v_i$ （$1\leq u_i,v_i\leq 2n$），表示一条连接节点 $u_i$ 和 $v_i$ 的边。保证这 $2n - 1$ 条边构成一棵树。 保证所有测试数据的 $n$ 之和不超过 $10^6$。

Output

对于每组测试数据，输出一个长度为 $n$ 的 $01$ 字符串。如果 cats 从拥有编号为 $i$ 的钥匙的节点出发，可以收集到全部的 $n$ 种钥匙，则字符串中第 $i$ 个字符为 $1$。否则字符串中第 $i$ 个字符为 $0$。

Sample Input

4
1
1 -1
1 2
3
-3 2 1 -1 3 -2
1 2
1 3
2 4
2 5
3 6
3
1 -1 2 -2 -3 3
1 2
2 3
3 4
4 5
5 6
3
1 -3 2 -2 -1 3
1 2
2 3
3 4
4 5
5 6

Sample Output

1
011
000
000

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（6）