알고리즘 수업 - 너비 우선 탐색 1

문제

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

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

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

입력

첫째 줄에 정점의 수 $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 5 1
1 2
1 4
2 3
2 4
3 4

예제 출력 1

1
2
4
3
0

힌트

시작 정점은 1번이다. 1번 정점과 인접한 정점은 2번, 4번이다. 오름차순으로 방문하므로 2번을 방문하고(방문 순서 2), 4번을 방문한다(방문 순서 3). 그 다음 2번 정점과 인접한 정점 중 아직 방문하지 않은 3번을 방문한다(방문 순서 4). 모든 인접한 정점을 방문한 후에도 5번 정점은 도달할 수 없으므로 방문 순서는 0이 된다.

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