Problem Statement

You are given a tree with $N$ vertices.

The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. Edge $i$ bidirectionally connects vertices $A_i$ and $B_i$.

Determine whether there exists a permutation $P$ obtained by rearranging $(1,2,\dots,N)$ that satisfies the following condition.

• For every tuple $(i,j,k)$ of distinct integers between $1$ and $N$, inclusive, at least one of the following $2$ conditions holds.

• The simple path from vertex $i$ to vertex $j$ does not contain vertex $k$.
• The simple path from vertex $P_i$ to vertex $P_j$ does not contain vertex $P_k$.

For each input file, solve $T$ test cases.

Constraints

Input

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$

Output

Print $T$ lines. On line $i\ (1\le i \le T)$, for the $i$-th test case, print Yes if a permutation $P$ satisfying the condition exists, and No otherwise.

Sample

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

Yes
No
No