题目背景

翻译自 CSES-1700 题。

题目描述

给定两棵有根树，你的任务是判断它们是否同构，也就是说，是否可以通过某种方式绘制它们，使它们看起来相同。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

接下来有 $t$ 个测试用例，每个测试用例描述如下：

• 第一行包含一个整数 $n$，表示两棵树的节点数。节点编号为 $1, 2, \dots, n$，且节点 $1$ 是根节点。
• 接下来有 $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

NO
YES

说明/提示

$1 \leq t \leq 1000$；

$2 \leq n \leq 10^5$；

所有测试用例中 $n$ 的总和不超过 $10^5$。