Cho một cây gồm ~N~ đỉnh và ~N - 1~ cạnh, có gốc là đỉnh ~1~. Hãy cho biết cây đã cho có phải là cây đối xứng hay không?

Một cây gọi là đối xứng nếu:

• Cây con ngoài cùng bên trái của gốc có hình dạng giống hệt cây con ngoài cùng bên phải của gốc.
• Cây con thứ hai bên trái của gốc có hình dạng giống hệt cây con thứ 2 bên phải của gốc.
• ..............
• Nếu số lượng con trực tiếp của gốc là lẻ thì cây con giữa phải là cây đối xứng.

Ví dụ:

Các cây sau là cây đối xứng

Các cây sau thì không

Input

• Dòng đầu tiên chứa số nguyên ~t(t ≤ 100)~ là số lượng test case.
• Trong mỗi test case:
  • Dòng đầu tiên là số tự nhiên ~N(N ≤ 2 \times 10^5)~ là số đỉnh của cây.
  • ~N - 1~ dòng tiếp theo là hai số nguyên ~u_i, v_i(1 ≤ u_i, v_i ≤ n)~ biểu thị có cạnh nối giữa ~u_i~ và ~v_i~ trong cây.
• Dữ liệu đảm bảo tổng ~N~ trong tất cả các test không quá ~2 \times 10^5.~

Output

• Gồm ~t~ dòng, dòng thứ ~i~ in ~YES~ nếu cây trong test case thứ ~i~ là cây đối xứng, ngược lại in ra ~NO.~

Example

Input

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

Output

YES
NO
YES
NO
NO
YES