알고리즘 수업 - 깊이 우선 탐색 1

문제

$N$개의 정점과 $M$개의 간선으로 구성된 무방향 그래프가 주어집니다. 정점 번호는 1번부터 $N$번까지이고, 모든 간선의 가중치는 1입니다.

시작 정점 $R$에서 시작하여 깊이 우선 탐색(DFS)으로 그래프의 정점들을 방문할 때, 각 정점의 방문 순서를 구하는 프로그램을 작성하세요.

단, 인접한 정점들을 방문할 때는 정점 번호가 작은 것을 먼저 방문(오름차순 방문)해야 합니다.

입력

첫째 줄에 정점의 수 $N$, 간선의 수 $M$, 시작 정점 $R$이 공백으로 구분되어 주어진다. $(5 \le N \le 100,000; 1 \le M \le 200,000; 1 \le R \le N)$

다음 $M$개의 줄 중 $i$번째 줄에는 간선의 양 끝점 $u_i$와 $v_i$가 공백으로 구분되어 주어진다. $(1 \le u_i < v_i \le N)$

모든 간선의 $(u_i, v_i)$ 쌍은 서로 다르며, 무방향 간선이다.

출력

첫째 줄부터 $N$개의 줄에 걸쳐 정답을 출력한다. $i$번째 줄에는 정점 $i$의 방문 순서를 출력한다. 시작 정점 $R$의 방문 순서는 1이다.

단, 시작 정점에서 방문할 수 없는 정점의 경우 0을 출력한다.

예제 입력 1

5 4 1
1 2
1 3
2 3
3 4

예제 출력 1

1
2
3
4
0

힌트

시작 정점은 1번이다. 1번 정점과 인접한 정점은 2번, 3번이다. 오름차순으로 2번을 먼저 방문한다(방문 순서 2). 2번 정점과 인접한 정점은 1번(방문됨), 3번이다. 3번을 방문한다(방문 순서 3). 3번 정점과 인접한 정점은 1번(방문됨), 2번(방문됨), 4번이다. 4번을 방문한다(방문 순서 4). 4번 정점은 더 이상 방문할 인접 정점이 없으므로 백트래킹한다. 모든 탐색을 마친 후에도 5번 정점은 도달할 수 없으므로 방문 순서는 0이 된다.

따라서 정점 1, 2, 3, 4, 5의 방문 순서는 각각 1, 2, 3, 4, 0이다.