#P18257. Reconstruction
Reconstruction
Reconstruction
Pig100ton 有一棵含 个顶点的树 ,以及一个长度为 、初始全部为 的数组 。他可以恰好执行 次以下操作,从 构造一棵新树 :
- 任意选择一个尚未从 中删除的顶点 ,令它在 中的父亲为 。如果 ,则令 为 的根。
- 对当前 中所有能够从 沿边到达的顶点 ,将 赋值为 。
- 从 中删除顶点 及其所有相邻边。
Pig100ton 还有另一棵含 个顶点的树 。
对于每个 ,请判断:当 以顶点 为根时,是否存在一种操作顺序,使得构造出的 恰好等于这棵有根树 ?
两棵输入树的顶点编号均为 ,相同编号表示同一个顶点。
输入格式
第一行包含一个整数 ,表示顶点数。
接下来 行,每行包含两个整数 ,表示 的一条无向边。
再接下来 行,每行包含两个整数 ,表示 的一条无向边。
保证每部分给出的边均构成一棵树。
输出格式
输出一行一个长度为 的字符串。
若以顶点 为根的 可以被构造出来,则第 个字符为 ,否则为 。
数据范围
- ;
- 每条边满足 且 ;
- 输入只有一组数据。
样例 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