#P18120. Leaf Meeting

Leaf Meeting

Leaf Meeting

给定一棵 nn 个顶点的无向树。度数为1的顶点称为叶子;每个叶子最初放有一个棋子。

对每个从叶子 vv 出发的棋子,独立选择一个无限的叶子序列 a1,a2,…a_1,a_2,\ldots,要求 a1≠va_1\ne v 且 ai≠ai+1a_i\ne a_{i+1}。棋子先沿最短路径从 vv 走向 a1a_1,再从 a1a_1 走向 a2a_2,如此无限继续。

每一步,所有棋子同时沿各自路线走过恰好一条边,不能停留。判断能否选择这些路线,使所有棋子在某个有限时刻同时位于同一个叶子。

输入格式

第一行整数 TT,1≤T≤100001\le T\le10000。

每组第一行整数 nn,2≤n≤2000002\le n\le200000。接下来 n−1n-1 行,每行两个顶点 u,vu,v,1≤u,v≤n1\le u,v\le n,保证构成一棵树。

所有数据的 nn 之和不超过200000。

输出格式

每组输出 YES 或 NO,表示是否存在符合要求的路线。

样例

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
NO
NO
NO
NO
YES