链接: https://cses.fi/problemset/task/1701

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定两棵（无根）树，你的任务是判断它们是否 同构，即是否可以将它们画成外观相同。

输入

第一行包含一个整数 $t$：测试组数。随后有 $t$ 组测试，描述如下：

第一行包含一个整数 $n$：两棵树中的节点数量。节点编号为 $1,2,\dots,n$。

接下来有 $n-1$ 行描述第一棵树的边，最后有 $n-1$ 行描述第二棵树的边。

输出

对于每组测试，如果两棵树同构，输出 "YES"，否则输出 "NO"。

数据范围

$1 \le t \le 1000$ $2 \le n \le 10^5$ 所有 $n$ 的和至多为 $10^5$

样例输入

2
3
1 2
2 3
1 2
1 3
3
1 2
2 3
1 3
3 2

样例输出

YES
YES