Với hai cây có gốc, tìm xem chúng có đẳng cấu hay không, tức là có thể vẽ sao cho chúng giống nhau.

Input

• Dòng đầu tiên chứa số nguyên \(t\): số test cases. Mỗi test cases được mô tả như sau:
• Dòng đầu tiên có số nguyên \(n\): số nút trong cả hai cây. Các nút được đánh số \(1,2,\dots,n\) và nút \(1\) là nút gốc.
• \(n - 1\) dòng tiếp theo mô tả các cạnh của cây thứ nhất.
• \(n - 1\) dòng tiếp theo mô tả các cạnh của cây thứ hai.

Constraints

• \(1 \leq t \leq 1000\)
• \(1 \leq n \leq 10^5\)
• Tổng của \(n\) trong các test cases \(\leq 10^5\)

Output

• Với mỗi test cases, in YES nếu 2 cây đẳng cấu, ngược lại, in NO.

Example

2
3
1 2
2 3
1 2
1 3
3
1 2
2 3
1 3
3 2

NO
YES