#P18257. Reconstruction

Reconstruction

Reconstruction

Pig100ton 有一棵含 nn 个顶点的树 T1T_1,以及一个长度为 nn、初始全部为 00 的数组 aa。他可以恰好执行 nn 次以下操作,从 T1T_1 构造一棵新树 T2T_2:

  1. 任意选择一个尚未从 T1T_1 中删除的顶点 xx,令它在 T2T_2 中的父亲为 axa_x。如果 ax=0a_x=0,则令 xx 为 T2T_2 的根。
  2. 对当前 T1T_1 中所有能够从 xx 沿边到达的顶点 yy,将 aya_y 赋值为 xx。
  3. 从 T1T_1 中删除顶点 xx 及其所有相邻边。

Pig100ton 还有另一棵含 nn 个顶点的树 TT。

对于每个 1≤u≤n1\le u\le n,请判断:当 TT 以顶点 uu 为根时,是否存在一种操作顺序,使得构造出的 T2T_2 恰好等于这棵有根树 TT?

两棵输入树的顶点编号均为 1,2,…,n1,2,\ldots,n,相同编号表示同一个顶点。

输入格式

第一行包含一个整数 nn,表示顶点数。

接下来 n−1n-1 行,每行包含两个整数 u,vu,v,表示 T1T_1 的一条无向边。

再接下来 n−1n-1 行,每行包含两个整数 u,vu,v,表示 TT 的一条无向边。

保证每部分给出的边均构成一棵树。

输出格式

输出一行一个长度为 nn 的字符串。

若以顶点 ii 为根的 TT 可以被构造出来,则第 ii 个字符为 11,否则为 00。

数据范围

  • 1≤n≤5×1051\le n\le5\times10^5;
  • 每条边满足 1≤u,v≤n1\le u,v\le n 且 u≠vu\ne v;
  • 输入只有一组数据。

样例 1

3
1 2
2 3
2 1
1 3
001

样例 2

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