Pig100ton 拥有一棵包含 $n$ 个顶点的树 $T_1$ 和一个长度为 $n$ 的数组 $a$，其元素初始值均为 $0$。他可以通过执行 $n$ 次以下操作来从 $T_1$ 构建一棵新树 $T_2$：

• 选择一个在 $T_1$ 中尚未被删除的任意顶点 $x$。令其在 $T_2$ 中的父亲为 $a_x$（若 $a_x = 0$，则令 $x$ 为 $T_2$ 的根）。
• 对于所有在 $T_1$ 中通过边可以从 $x$ 到达的顶点 $y$，将 $x$ 赋值给 $a_y$。
• 删除顶点 $x$ 以及 $T_1$ 中与 $x$ 相连的边。

Pig100ton 还有另一棵包含 $n$ 个顶点的树 $T$。对于每个 $1 \le u \le n$，他想知道如果以 $u$ 为根，树 $T$ 是否为他可以从 $T_1$ 构建出的树。请帮他找出答案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示树 $T_1$ 中的顶点数。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示 $T_1$ 中连接 $u$ 和 $v$ 的一条无向边。保证给定的边构成一棵树。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示 $T$ 中连接 $u$ 和 $v$ 的一条无向边。保证给定的边构成一棵树。

输出格式

输出一行长度为 $n$ 的字符串。如果以 $i$ 为根时 $T$ 是可以由 $T_1$ 构建出的树，则第 $i$ 个字符为 '1'，否则为 '0'。

样例

样例输入 1

3
1 2
2 3
2 1
1 3

样例输出 1

001

样例输入 2

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

样例输出 2

010110