Code Submission Evaluation System Login

CSES Problem Set

Tree Isomorphism II


Task | Statistics


CSES - Tree Isomorphism IICSES - Tree Isomorphism II

Time limit:1.00 s Memory limit:512 MB

Given two (not rooted) trees, your task is to find out if they are isomorphic, i.e., it is possible to draw them so that they look the same.

Input

The first input line has an integer $t$: the number of tests. Then, there are $t$ tests described as follows:

The first line has an integer $n$: the number of nodes in both trees. The nodes are numbered $1,2,\dots,n$.

Then, there are $n-1$ lines describing the edges of the first tree, and finally $n-1$ lines describing the edges of the second tree.

Output

For each test, print "YES", if the trees are isomorphic, and "NO" otherwise.

Constraints
Example

Input:
2
3
1 2
2 3
1 2
1 3
3
1 2
2 3
1 3
3 2


Output:
YES
YES