무방향 그래프와 시작 정점 \(R\)이 주어진다. 정점 \(R\)에서 깊이 우선 탐색을 시작한다.

한 정점에서 방문할 수 있는 정점이 여러 개라면, 입력에서 먼저 주어진 간선으로 연결된 정점부터 방문한다.

즉, 정점 \(x\)에 연결된 간선들 중 입력에서 더 앞에 주어진 간선을 따라 먼저 이동을 시도한다. 각 정점이 몇 번째로 방문되었는지 구해 보자.

입력

첫째 줄에 정점의 개수 \(N\), 간선의 개수 \(M\), 시작 정점 \(R\)이 공백으로 구분되어 주어진다.

다음 \(M\)개의 줄에 간선의 양 끝점 \(u\), \(v\)가 공백으로 구분되어 주어진다. 간선은 이 순서대로 입력된 것으로 본다.

출력

\(N\)개의 줄에 걸쳐 출력한다. \(i\)번째 줄에는 정점 \(i\)의 방문 순서를 출력한다. 시작 정점은 \(1\)번째로 방문한다. 시작 정점에서 도달할 수 없는 정점은 0을 출력한다.

제한

• \(1 \le N \le 1,000\)
• \(0 \le M \le 100,000\)
• \(1 \le R \le N\)
• 정점에는 \(1\)부터 \(N\)까지 번호가 매겨져 있다.
• 모든 간선은 무방향 간선이다.
• 셀프 루프는 없다.
• 같은 두 정점을 잇는 간선은 두 개 이상 주어지지 않는다.

예제 입력 1

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

예제 출력 1

1
3
4
2
0

예제 입력 2

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

예제 출력 2

3
4
1
0
0
2