시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB61231836.000%

문제

You are given two undirected simple connected graphs $G$ and $G'$. Each graph consists of $N$ vertices numbered from $1$ to $N$ and $N$ edges.

Are these graphs isomorphic? In other words, is there a permutation $(p_1, \dots , p_N)$ of $(1, \dots , N)$ such that $G$ has an edge which connects two vertices $u$ and $v$ if and only if $G'$ has an edge which connects $p_u$ and $p_v$?

입력

The input consists of a single test case of the following format.

$N$

$a_1$ $b_1$

$\vdots$

$a_N$ $b_N$

$c_1$ $d_1$

$\vdots$

$c_N$ $d_N$

The first line contains a single integer $N$ ($3 ≤ N ≤ 2 \times 10^5$), which represents the number of vertices of graphs $G$ and $G'$. Each of the next $N$ lines contains two integers $a_i$ and $b_i$ ($1 ≤ a_i, b_i ≤ N$), which represent that there is an undirected edge connecting vertices $a_i$ and $b_i$ of $G$. Similarly, each of the next $N$ lines contains two integers $c_i$ and $d_i$ ($1 ≤ c_i, d_i ≤ N$), which represent that there is an undirected edge connecting vertices $c_i$ and $d_i$ of $G'$. You can assume that both $G$ and $G'$ are connected graphs and do not contain self-loops and double edges.

출력

Print “Yes" if $G$ and $G'$ are isomorphic. Print “No", otherwise.

예제 입력 1

4
1 2
2 3
2 4
3 4
1 2
1 3
1 4
3 4

예제 출력 1

Yes

예제 입력 2

4
1 2
2 3
3 4
1 4
1 2
1 3
1 4
3 4

예제 출력 2

No

예제 입력 3

6
1 2
1 3
2 5
2 6
3 5
4 6
1 5
1 6
2 4
2 5
2 6
3 4

예제 출력 3

Yes