| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 61 | 23 | 18 | 36.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.
4 1 2 2 3 2 4 3 4 1 2 1 3 1 4 3 4
Yes
4 1 2 2 3 3 4 1 4 1 2 1 3 1 4 3 4
No
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
Yes