配点 : 400 点
問題文
带根树 S 对于带根树 f(S) ,S 假设进行了以下操作。
- 木 S 的所有叶子 S 自身进行替换
带根树 S 对于 (S_1, S_2, \dots) 定义树的无限序列如下。
- S_1 := S
- S_i := f(S_{i-1}) \quad (i > 1)
無限木 S_{\infty}:= \displaystyle\lim_{n\to\infty} S_n 该值应乘以 S 从中导出的 分形树 称为。
K 个带根树 T_1, T_2, \dots, T_K 。 对于 T_i\,(i=1,2,\dots,K) 是满足以下条件的带根树。
- 顶点数为 N_i \geq 2
- 在顶点 1,2,\dots,N_i 被编号
- 根是顶点 1 是
- j=2,3,\dots,N_i 关于,向上游 j 的父级是顶点 p_{i,j} 是
各 (i,j) \, (i,j=1,2,\dots,K) , 当我输入 T_i,\,T_j 从各自导出的分形树 (T_i)_\infty 和 按字典顺序比较 (T_j)_\infty 判断是否同构。
分形树同构性的定义
分形树 T 的顶点集 V(T) ,边集合为 E(T) 为例。两个分形树 S,T 同构的意思是存在一个满足以下两个条件的全单射 \varphi:V(S)\to V(T) 。- \{u,v\}\in E(S) \iff \{\varphi(u),\varphi(v)\}\in E(T)
- S,T 的根分别是 r_S, r_T 当\varphi(r_S)=r_T
制約
- 2 \leq K \leq 1000
- 2 \leq N_i \leq 5 \times 10^4 \quad (1 \leq i \leq K)
- \displaystyle\sum_{i=1}^K N_i \leq 10^5
- 1 \leq p_{i,j} < j \quad (1 \leq i \leq K,\,2\leq j \leq N_i)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
K
N_1 p_{1,2} p_{1,3} \dots p_{1,N_1}
N_2 p_{2,2} p_{2,3} \dots p_{2,N_2}
\vdots
N_K p_{K,2} p_{K,3} \dots p_{K,N_K}
出力
K 行。 i 长度 K 可以得到第 0 或
至少 1 生成的字符串。
i 线 j 第一个字符是 (T_i)_\infty 和
按字典顺序比较 (T_j)_\infty 如果同构 1,如果不同构 0 。
入力例 1
4 2 1 3 1 2 3 1 1 5 1 1 2 2
出力例 1
1100 1100 0011 0011
给定的树如下。

对这些树 1 次操作后得到的树如下。
