$n$ 頂点からなる無向木が与えられます。葉とは次数が $1$ の頂点です。葉の数を $k$ とします。最初、各葉にはコマが $1$ 個ずつ置かれているので、コマは全部で $k$ 個あります。

各コマについて、すべての $i\ge 1$ に対して $a_i\ne a_{i+1}$ を満たし、さらに $a_1\ne v$ を満たす葉の無限列 $a_1,a_2,a_3,\ldots$ を選ばなければなりません。ここで $v$ はそのコマが最初に置かれている葉です。異なるコマの列は独立に選ぶことができます。選んだ列によってコマの経路が決まります。まず $v$ から $a_1$ への最短経路を進み、次に $a_1$ から $a_2$ への最短経路を進み、その次に $a_2$ から $a_3$ へ進み、これを無限に繰り返します。

1 回の移動で、すべてのコマはそれぞれの経路上の辺をちょうど $1$ 本、同時に通過します。どのコマもその場にとどまることはできません。

有限回の移動の後に、$k$ 個のコマすべてが同時に同じ葉にいるように、各列を選べるかどうか判定してください。

入力

最初の行には、テストケースの数を表す整数 $t$（$1\le t\le 10^4$）が $1$ 個含まれます。

各テストケースの最初の行には、木の頂点数を表す整数 $n$（$2\le n\le 2\cdot 10^5$）が含まれます。

続く $n-1$ 行には、それぞれ $2$ 個の整数 $u,v$（$1\le u,v\le n$）が含まれ、頂点 $u$ と $v$ を結ぶ双方向の辺を表します。これらの辺が木を形成することが保証されます。

すべてのテストケースにわたる $n$ の合計は $2\cdot 10^5$ 以下であることが保証されます。

出力

各テストケースについて、答えを別々の行に出力してください。すべてのコマが同時に $1$ つの葉に集まるように、すべてのコマに対して条件を満たす列を選べる場合は 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