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
nadstratosfer:
20190708 06:48:45
Since the trees are undirected, aren't we simply supposed to check whether T1 and T2 are made of the same set of edges? Eg. can two trees be isomorphic if there's an edge between u and v in T1 but not in T2? 

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. 
Added by:  Andrey Naumenko 
Date:  20101110 
Time limit:  0.261s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 