CF1800G.Symmetree

Kid was gifted a tree of $n$ vertices with the root in the vertex $1$. Since he really like symmetrical objects, Kid wants to find out if this tree is symmetrical.

For example, the trees in the picture above are symmetrical.

And the trees in this picture are not symmetrical.

Formally, a tree is symmetrical if there exists an order of children such that:

• The subtree of the leftmost child of the root is a mirror image of the subtree of the rightmost child;
• the subtree of the second-left child of the root is a mirror image of the subtree of the second-right child of the root;
• ...
• if the number of children of the root is odd, then the subtree of the middle child should be symmetrical.

Kid 收到一棵包含 $n$ 个顶点的树，根节点为顶点 $1$。由于他非常喜欢对称的物体，Kid 想要判断这棵树是否对称。

例如，上图中的树是对称的。

而此图中的树则不对称。

形式化地，一棵树是对称的，当且仅当存在一种子节点的排列顺序，使得：

• 根节点最左侧子节点的子树与最右侧子节点的子树互为镜像；
• 根节点第二左子节点的子树与第二右子节点的子树互为镜像；
• ……
• 若根节点的子节点数目为奇数，则中间那个子节点所对应的子树本身必须是对称的。

The first line of input data contains single integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The first line of each case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The following $n-1$ lines contain two integers each $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) — indices of vertices connected by an edge.

It is guaranteed that the sum of $n$ over all cases does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 表示树中顶点的数量。

接下来的 $n-1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，且 $u \neq v$）—— 表示由一条边连接的两个顶点的编号。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

Output $t$ strings, each of which is the answer to the corresponding test case. As an answer, output "YES" if this tree is symmetrical, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

输出 $t$ 个字符串，每个字符串对应一个测试用例的答案。若该树是轴对称的，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出答案（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答）。