TREEISO - Tree Isomorphism

no tags 

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 N-1 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 N-1 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: 2019-07-08 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: 2017-08-31 01:52:38

Andrey, is the time limit really okay for Java?

Medo: 2015-06-23 03:47:53

Medo: (edit) 2015-06-23 03:47:53
Time limit is too strict. Not even a single accepted solution in JAVA. Don't waste your time, and code it in C/C++ from the beginning.

Last edit: 2015-06-23 04:24:06
Carlo: 2015-04-15 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: 2014-05-27 15:12:28

I'm getting SIGABRT at test 7, why is that happening?

Andrey Naumenko: 2012-12-05 09:42:26

New tests added.

van Helsing: 2012-11-05 04:14:16

Test cases are weak.

:D: 2010-12-08 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: 2010-11-24 13:15:07

What is the expected complexity for this problem?Will O(N^2) per case suffice?

:D: 2010-11-22 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:2010-11-10
Time limit:0.261s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64