给定一棵有 $n$ 个顶点的无向树。叶子是度数为 $1$ 的顶点。设叶子的数量为 $k$；初始时，每个叶子上有一个棋子，因此共有 $k$ 个棋子。

对于每个棋子，你必须选择一个无限的叶子序列 $a_1, a_2, a_3, \ldots$，满足对所有 $i \ge 1$ 都有 $a_i \ne a_{i+1}$，且 $a_1 \ne v$，其中 $v$ 是该棋子初始所在的叶子。不同棋子的序列可以独立选择。所选序列决定了棋子的路线：它先沿最短路径从 $v$ 走到 $a_1$，然后沿最短路径从 $a_1$ 走到 $a_2$，再从 $a_2$ 走到 $a_3$，如此无限继续。

每次移动中，所有棋子同时沿各自的路线恰好走过一条边。任何棋子都不能停留在原地。

判断是否可以选择这些序列，使得在有限次移动之后，全部 $k$ 个棋子在同一时刻位于同一个叶子上。

输入格式

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

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

接下来的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示顶点 $u$ 和 $v$ 之间的一条双向边。保证这些边构成一棵树。

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

输出格式

对于每个测试用例，在单独的一行输出答案。如果可以为所有棋子选择满足要求的序列，使它们在同一时刻聚集在同一个叶子上，输出 YES；否则输出 NO。

样例

输入格式 1

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

输出格式 1

NO
NO
NO
NO
YES