Given two undirected trees T1 and T2 with equal number of vertices N (1 ≤ N ≤ 100,000) numbered 1 to N, find out if they are isomorphic.

Two trees T1 and T2 are isomorphic if there is a bijection f between the vertex sets of T1 and T2 such that any two vertices u and v of T1 are adjacent in T1 if and only if f(u) and f(v) are adjacent in T2.

\n

Input

\n

The first line of input contains the number of test cases nTest (1<= nTest <= 400). Each test case contains:

\n

The first line contains the number of nodes N.
Each of next N-1 lines contain two integers A, B, denoting that there is an edge in T1 between nodes A and B (1 ≤ A, B ≤ N).
Each of next N-1 lines contain two integers A, B, denoting that there is an edge in T2 between nodes A and B (1 ≤ A, B ≤ N).

\n

The sum of N over all test cases will not exceed 100,000.

\n

Output

\n

For each test case print YES if T1 and T2 are isomorphic and NO otherwise.

\n

Example

\n

Input:\n2
4
4 2
4 1
2 3
4 2
2 3
4 1
5
3 4
3 2
3 5
3 1
3 4
4 2
2 5
2 1\n\nOutput:\nYES
NO\n

统计

递交统计

Tree Isomorphism

信息

状态

开发

支持

还没有账户？

登录