题目描述
给定两棵有根树 T1,T2,其中根节点为 1 号点。你需要判定 T1,T2 在无标号意义下是否同构。
输入格式
每个测试点中包含多组测试数据。
输入的第一行包含一个整数 T,表示数据组数。对于每组数据:
输入的第一行包含一个整数 n。
接下来 n−1 行,每行两个整数 (u,v),描述 T1 中的一条边。
接下来 n−1 行,每行两个整数 (u,v),描述 T2 中的一条边。
输出格式
对于每组数据,若 T1,T2 同构,输出 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≤n≤105,1≤∑n≤106。