동형 그래프 판별

시간 제한2초메모리 제한1024 MB

요약

정점이 N개이고 간선이 N개인 두 연결 그래프가 서로 동형인지 판별합니다.

난이도: 보통10점 중 6점
유형: 그래프, 트리, 문자열 매칭, 해시맵
정답자: 아직 제출이 없습니다

문제

두 개의 무방향 단순 연결 그래프 $G$ 와 $G'$ 가 주어진다. 각 그래프는 1부터 $N$ 까지 번호가 매겨진 $N$ 개의 정점과 $N$ 개의 간선으로 이루어져 있다.

두 그래프가 동형인지 판별하라. 즉, $(1, 2, \dots, N)$ 의 순열 $(p_1, p_2, \dots, p_N)$ 이 존재하여, 모든 정점 쌍 $u$ , $v$ 에 대해 $G$ 에서 $u$ 와 $v$ 사이에 간선이 있을 때에만 $G'$ 에서 $p_u$ 와 $p_v$ 사이에 간선이 있는지 확인하라.

입력

첫 줄에 정수 $N$ 이 주어진다 ( $3 \le N \le 2 \times 10^5$ ).

다음 $N$ 개의 줄에는 $G$ 에서 정점 $a_i$ 와 $b_i$ 를 잇는 무방향 간선을 나타내는 두 정수 $a_i$ , $b_i$ ( $1 \le a_i, b_i \le N$ )가 주어진다.

그다음 $N$ 개의 줄에는 $G'$ 에서 정점 $c_i$ 와 $d_i$ 를 잇는 무방향 간선을 나타내는 두 정수 $c_i$ , $d_i$ ( $1 \le c_i, d_i \le N$ )가 주어진다.

두 그래프 모두 연결되어 있으며, 자기 루프와 중복 간선은 없다.

N
a_1 b_1
...
a_N b_N
c_1 d_1
...
c_N d_N

출력

$G$ 와 $G'$ 가 동형이면 Yes, 아니면 No를 출력한다.

예제3

예제 1
입력
```
4
1 2
2 3
2 4
3 4
1 2
1 3
1 4
3 4
```
예상 출력
```
Yes
```
예제 2
입력
```
4
1 2
2 3
3 4
1 4
1 2
1 3
1 4
3 4
```
예상 출력
```
No
```

예제 3

입력

예상 출력

Yes