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
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.

acheron: 2010-11-22 14:47:31

Are there other problems involving tree isomorphism ?


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