Isomorphic Graph

fsshakkhor The Tough Winter Spar, 20...
Limits 1s, 512 MB

You are given two connected graphs $G_1$ and $G_2$. Both of the graphs have $N$ vertices and $N$ 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 $G$ and $H$ with vertices $V_n = \{1, 2, ... , n\}$ are said to be isomorphic if there is a permutation $p$ of $V_n$ such that $\{u, v\}$ is in the set of graph edges $E(G)$ if and only if $\{p(u), p(v)\}$ is in the set of graph edges $E(H)$.

Input

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

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

Each of the next $N$ lines contain two integers $U$ and $V$, denoting that there is an edge between vertex $U$ and $V$ in graph $G_1$.

Each of the next $N$ lines contain two integers $U$ and $V$, denoting that there is an edge between vertex $U$ and $V$ in graph $G_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

  • $1 ≤ T ≤ 100$.
  • $3 ≤ N ≤ 10^5$.
  • $1 ≤ U,V ≤ N$.
  • Sum of $N$ over all test cases will not exceed $5 \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

Submit

Login to submit.

Statistics

42% Solution Ratio
NirjhorEarliest, Dec '19
AnachorFastest, 0.2s
NirjhorLightest, 13 MB
adamantShortest, 1933B
Toph uses cookies. By continuing you agree to our Cookie Policy.