Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Isomorphic Graph

By fsshakkhor · Limits 1s, 512 MB

You are given two connected graphs G1G_1 and G2G_2. Both of the graphs have NN vertices and NN number of edges.
You have to say whether the two graphs are isomorphic or not.

Two graphs are isomorphic if the vertex set of one graph can be relabeled in such a way that the set of edges of both graphs becomes the same.
Formally, Two graphs GG and HH with vertices Vn={1,2,...,n}V_n = \{1, 2, ... , n\} are said to be isomorphic if there is a permutation pp of VnV_n such that {u,v}\{u, v\} is in the set of graph edges E(G)E(G) if and only if {p(u),p(v)}\{p(u), p(v)\} is in the set of graph edges E(H)E(H).

Input

First-line contains an integer TT, denoting the number of test cases.

Each test case starts with an integer NN, denoting the number of vertices and edges.

Each of the next NN lines contain two integers UU and VV, denoting that there is an edge between vertex UU and VV in graph G1G_1.

Each of the next NN lines contain two integers UU and VV, denoting that there is an edge between vertex UU and VV in graph G2G_2.

It is guaranteed that both of the given graphs are connected. Also, the graphs do not contain any self-loop or parallel edges.

Constraints

  • 1T1001 ≤ T ≤ 100.
  • 3N1053 ≤ N ≤ 10^5.
  • 1U,VN1 ≤ U,V ≤ N.
  • Sum of NN over all test cases will not exceed 5×1055 \times 10^5.

Output

For each test case, print "Yes" if the given graphs are isomorphic. Otherwise, print "No".

Sample

InputOutput
1
3
1 2
1 3
2 3
2 1
3 2
1 3
Yes

Discussion

Statistics


42% Solution Ratio

NirjhorEarliest, Dec '19

AnachorFastest, 0.2s

NirjhorLightest, 13 MB

adamantShortest, 1933B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.