TREEISO  Tree Isomorphism
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.
Input
The first line of input contains the number of test cases nTest (1<= nTest <= 400). Each test case contains:
 The first line contains the number of nodes N.
 Each of next N1 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 N1 lines contain two integers A, B, denoting that there is an edge in T2 between nodes A and B (1 ≤ A, B ≤ N).
The sum of N over all test cases will not exceed 100,000.
Output
For each test case print YES if T1 and T2 are isomorphic and NO otherwise.
Example
Input: 2
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 Output: YES
NO
hide comments
jecht:
20170831 01:52:38
Andrey, is the time limit really okay for Java? 

Medo:
20150623 03:47:53
Medo: (edit) 20150623 03:47:53


Carlo:
20150415 18:25:34
I wrote Ahu Algorithm in O(NlogN) and it gets TLE, and I wrote the "naive" O(N^2) solution and gets accepted. wat? 

saadtaame:
20140527 15:12:28
I'm getting SIGABRT at test 7, why is that happening? 

Andrey Naumenko:
20121205 09:42:26
New tests added. 

van Helsing:
20121105 04:14:16
Test cases are weak. 

:D:
20101208 12:42:07
Mine was O(n*log(n)), but it was much faster in general case. I read on the forum, that there is a O(n) algo. Even for N=10000, N^2 would be too big. 

Ravi Kiran:
20101124 13:15:07
What is the expected complexity for this problem?Will O(N^2) per case suffice? 

:D:
20101122 19:37:44
I recall a graph isomorphism problem: TRANSL. Also a problem somewhat along the lines of isomorphism: PAIRGRPH. 

acheron:
20101122 14:47:31
Are there other problems involving tree isomorphism ? 
Added by:  Andrey Naumenko 
Date:  20101110 
Time limit:  0.261s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 