题目描述
给定两棵有根树 $T_1, T_2$,其中根节点为 $1$ 号点。你需要判定 $T_1, T_2$ 在无标号意义下是否同构。
输入格式
每个测试点中包含多组测试数据。
输入的第一行包含一个整数 $T$,表示数据组数。对于每组数据:
输入的第一行包含一个整数 $n$。
接下来 $n-1$ 行,每行两个整数 $(u,v)$,描述 $T_1$ 中的一条边。
接下来 $n-1$ 行,每行两个整数 $(u,v)$,描述 $T_2$ 中的一条边。
输出格式
对于每组数据,若 $T_1, T_2$ 同构,输出 Isomorphism
,否则输出 No
。
样例数据
样例输入
5
3
1 2
1 3
1 2
2 3
3
1 2
1 3
1 3
1 2
4
1 2
2 3
2 4
1 4
4 2
4 3
4
1 2
2 3
3 4
1 2
2 3
2 4
5
1 2
1 3
2 4
2 5
1 4
1 5
2 5
3 5
样例输出
No
Isomorphism
Isomorphism
No
Isomorphism
子任务
对于所有数据,$1 \leq n \leq 10^5, 1 \leq \sum n \leq 10^6$。