충전소 점검의 마지막 도착지

문제

한 지역의 전기차 충전소 N개에는 1번부터 N번까지 번호가 붙어 있다. 충전소 사이에는 점검 차량이 이용할 수 있는 연결 도로 M개가 있다. 각 도로는 서로 다른 두 충전소를 직접 연결하며, 어느 방향으로든 통과할 수 있다. 같은 두 충전소 사이에 도로가 여러 개 있을 수도 있다. 지도에 표시된 연결 도로 이외의 경로로는 충전소 사이를 이동할 수 없다. 점검 차량은 S번 충전소에서 출발한다. 차량이 연결 도로 하나를 통과하는 데에는 정확히 1분이 걸린다. 충전소 내부에서의 이동이나 점검에는 시간이 들지 않으며, 이동 중에 충전이 필요하거나 도로가 막히는 일은 없다. 따라서 특정 충전소에 도착하는 데 필요한 최소 시간은 출발지에서 그 충전소까지 통과해야 하는 도로 수의 최솟값과 같다. 관리자는 출발지를 제외한 충전소 중에서 가장 늦게 도착할 수밖에 없는 충전소를 우선 점검 대상으로 정한다. 정확히는 S번에서 도달할 수 있는 각 충전소의 최소 도착 시간을 구한 뒤, 그 값이 가장 큰 충전소를 선택한다. 일부러 돌아가는 경로를 선택해서 도착을 늦추는 것은 고려하지 않는다. 도달할 수 없는 충전소는 후보에 포함하지 않는다. 최소 도착 시간이 가장 큰 충전소가 여러 개이면 번호가 가장 작은 충전소를 선택한다. 선택한 충전소 번호와 그곳까지의 최소 도착 시간을 구한다. 출발지에서 다른 충전소로 하나도 이동할 수 없으면 점검 대상을 정할 수 없으므로 -1만 출력한다. 하나의 경로에서 지나간 충전소를 다시 방문할 수 있지만, 최소 도착 시간을 구할 때 불필요한 재방문을 할 필요는 없다.

입력

첫째 줄에 정수 N, M, S가 공백으로 구분되어 주어진다. 다음 M개 줄에는 도로 양 끝의 충전소 번호 u, v가 주어진다.
1 ≤ N ≤ 20,000
0 ≤ M ≤ 30,000
1 ≤ S ≤ N
1 ≤ u, v ≤ N, u ≠ v
같은 두 충전소를 잇는 도로가 여러 번 주어질 수 있다. N = 1이면 M = 0이다. 모든 수는 정수다.

출력

점검 대상을 정할 수 있으면 충전소 번호와 최소 도착 시간(분)을 공백으로 구분하여 한 줄에 출력한다. 출발지를 제외하고 도달할 수 있는 충전소가 없으면 -1을 출력한다.

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

2 2

4 2 4
1 2
2 3

-1

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

3 2

출처: Devin.KR 자체 제작