QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB
Statistics

题目描述

给定两棵有根树 $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$。