QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB
[+5]

# 499. 树 Hash

Statistics

题目描述

给定两棵有根树 T1,T2,其中根节点为 1 号点。你需要判定 T1,T2 在无标号意义下是否同构。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含一个整数 T,表示数据组数。对于每组数据:

输入的第一行包含一个整数 n

接下来 n1 行,每行两个整数 (u,v),描述 T1 中的一条边。

接下来 n1 行,每行两个整数 (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

子任务

对于所有数据,1n105,1n106