题目背景

翻译自 CSES-1701 题。

题目描述

给定两棵（未根）树，你的任务是判断它们是否是同构的，即是否可以通过重新排列它们的节点，使得它们看起来相同。

输入格式

第一行包含一个整数 $t$，表示测试的数量。接下来，有 $t$ 个测试用例，每个测试用例的描述如下：

• 第一行包含一个整数 $n$，表示两棵树的节点数。节点编号为 $1, 2, \ldots, n$。
• 接下来 $n-1$ 行描述第一棵树的边，最后 $n-1$ 行描述第二棵树的边。

输出格式

对于每个测试用例，如果两棵树是同构的，输出 YES，否则输出 NO。

样例

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

YES
YES

数据范围

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