8806: [CSES Problem Set] Tree Isomorphism II
[Creator : ]
Description
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,…,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.
The first line has an integer n: the number of nodes in both trees. The nodes are numbered 1,2,…,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
$1≤t≤1000$
$2≤n≤10^5$
the sum of all values of $n$ is at most $10^5$
$2≤n≤10^5$
the sum of all values of $n$ is at most $10^5$
Sample 1 Input
2
3
1 2
2 3
1 2
1 3
3
1 2
2 3
1 3
3 2
Sample 1 Output
YES
YES