#CS1700. 树同构 I

树同构 I

题目背景

翻译自 CSES-1700 题。

题目描述

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

输入格式

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

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

• 第一行包含一个整数 n，表示两棵树的节点数。节点编号为 1,2,…,n1, 2, \dots, n1,2,…,n，且节点 1 是根节点。

• 接下来有 n−1n - 1n−1 行，描述第一棵树的边。

• 然后有 n−1n - 1n−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 10$

$2 \leq n \leq 10^5$

所有测试用例中 n 的总和不超过 10510^5105。