孩子获得了一棵由 $$$n$$$ 顶点组成的树,根位于顶点 $$$1$$$。由于孩子非常喜欢对称的物体,所以他想知道这棵树是否对称。
比如上图中的树是对称的。
而且这张图中的树木并不对称。
形式上,如果存在满足以下条件的子级顺序,则树是对称的:
- 根的最左边子树的子树是最右边子树的镜像;
- 根的左第二个孩子的子树是根的右第二个孩子的子树的镜像;
- ...
- 如果根的子树数量是奇数,则中间子树的子树应该是对称的。
输入
输入数据的第一行包含单个整数 $$$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$$$。
输出
输出$$$t$$$字符串,每个字符串都是对应测试用例的答案。作为答案,如果该树是对称的,则输出“YES”,否则输出“NO”。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
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
输出 #1
YES NO YES NO NO YES