SP7826 TREEISO - Tree Isomorphism

Given two undirected trees $T_1$ and $T_2$ with equal number of vertices $N$ ($1 \le N \le 100,000$) numbered $1$ to $N$, find out if they are isomorphic. Two trees $T_1$ and $T_2$ are isomorphic if there is a bijection $f$ between the vertex sets of $T_1$ and $T_2$ such that any two vertices $u$ and $v$ of $T_1$ are adjacent in $T_1$ if and only if $f(u)$ and $f(v)$ are adjacent in $T_2$.

The first line of input contains the number of test cases $\text{nTest}$ ($1 \le \text{nTest} \le 400$). Each test case contains: - 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 $T_1$ between nodes $A$ and $B$ ($1 \le A, B \le N$). - Each of next $N-1$ lines contain two integers $A, B$, denoting that there is an edge in $T_2$ between nodes $A$ and $B$ ($1 \le A, B \le N$). The sum of $N$ over all test cases will not exceed $100,000$.

For each test case print `YES` if $T_1$ and $T_2$ are isomorphic and `NO` otherwise.