Cho hai cây (không có gốc), nhiệm vụ của bạn là kiểm tra xem chúng có đẳng cấu hay không, tức là, có thể vẽ chúng sao cho chúng trông giống nhau.

Input

Dòng đầu vào đầu tiên có một số nguyên \(t\): số lượng test. Sau đó, có \(t\) test được mô tả như sau:

Dòng đầu tiên có một số nguyên \(n\): số nút trong cả hai cây. Các nút được đánh số \(1, 2, \ldots, n\).

Sau đó, có \(n − 1\) dòng mô tả các cạnh của cây thứ nhất, và cuối cùng là \(n − 1\) dòng mô tả các cạnh của cây thứ hai.

Output

Đối với từng test, in YES nếu các cây đẳng cấu và NO nếu ngược lại.

Constraints

• \(1 \leq t \leq 1000\)
• \(2 \leq n \leq 10 ^ 5\)
• Tổng của tất cả các giá trị của \(n\) nhiều nhất là \(10 ^ 5\)

Example

Input:

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

Output:

YES  
YES