問題文

$N$ 頂点からなる木が与えられます。

頂点には $1$ から $N$ の、辺には $1$ から $N-1$ の番号がついており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結んでいます。

$(1,2,\dots,N)$ を並び替えて得られる順列 $P$ であって以下の条件を満たすものが存在するか判定してください。

• 任意の $1$ 以上 $N$ 以下の相異なる整数の組 $(i,j,k)$ について以下の $2$ つの条件のうち少なくとも一方が成り立つ。

• 頂点 $i$ から頂点 $j$ への単純パスに頂点 $k$ が含まれない。
• 頂点 $P_i$ から頂点 $P_j$ への単純パスに頂点 $P_k$ が含まれない。

一つの入力ファイルにつき、 $T$ 個のテストケースに答えてください。

制約

入力

$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}$

出力

$T$ 行出力してください。 $i\ (1\le i \le T)$ 行目には $i$ 番目のテストケースについて、条件を満たす順列 $P$ が存在するならば Yes を、そうでなければ No を出力してください。

サンプル

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