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\le 100)$ là số lượng test case.
• Trong mỗi test case:
  • Dòng đầu tiên là số tự nhiên $N(N\le 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\le u_i,v_i\le 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