对称树

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一棵以结点 $1$ 为根、共有 $n$ 个结点的树。你可以任意排列每个结点的子结点顺序。

如果存在一种排列，使整棵有根树关于穿过根结点的竖直轴左右对称，则称这棵树是对称的。换言之，对任意结点，其最左侧子树应与最右侧子树互为镜像，次左侧与次右侧互为镜像；若子树数量为奇数，正中间的子树还必须自身对称。

请判断每个测试用例中的树是否对称。

输入格式

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

每个测试用例的第一行包含整数 $n$。接下来 $n-1$ 行每行包含两个整数 $u,v$，表示树的一条边。

输出格式

对每个测试用例输出一行。若树对称，输出 YES；否则输出 NO。

样例输入

6
6
1 5
1 6
1 2
2 3
2 4
7
1 5
1 3
3 6
1 4
4 7
4 2
9
1 2
2 4
2 3
3 5
1 7
7 6
7 8
8 9
10
2 9
9 10
2 3
6 7
4 3
1 2
3 8
2 5
6 5
10
3 2
8 10
9 7
4 2
8 2
2 1
4 5
6 5
5 7
1

样例输出

YES
NO
YES
NO
NO
YES

数据范围

对所有数据，$1\le t\le 10^4$，$1\le n\le 2\times 10^5$，所有测试用例的 $n$ 之和不超过 $2\times 10^5$；输入保证每个测试用例给出一棵树。