## 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 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 1Output:YES

NO

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 |