题目背景

翻译自 CSES-1701 题。

题目描述

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

输入格式

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

• 第一行包含一个整数 $n$，表示两棵树的节点数。节点编号为 $1, 2, \dots, 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 \leq t \leq 1000$;

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

所有 $n$ 的总和最多为 $10^5$。