서가 점검의 마지막 위치

문제

도서관은 서가 사이에 설치된 연결 통로를 이용하여 점검 카트를 움직인다. 서가에는 1번부터 N번까지 번호가 붙어 있다. 각 통로는 서로 다른 두 서가를 연결하며, 양방향으로 이동할 수 있다. 통로 하나를 지나는 데에는 정확히 1분이 걸린다. 같은 두 서가를 직접 연결하는 통로는 최대 하나이며, 모든 서가가 서로 연결되어 있다는 보장은 없다. 카트는 S번 서가에서 출발한다. 이번 점검에서는 출발한 뒤 L분 이내에 도착할 수 있는 서가만 점검 후보로 삼는다. 어떤 서가에 여러 경로로 갈 수 있으면 가장 짧게 걸리는 시간을 그 서가의 도착 시간으로 정한다. 따라서 후보 여부는 카트가 실제로 방문하는 순서가 아니라, S번 서가에서 각 서가까지 이동하는 데 필요한 최소 시간으로 결정된다. 출발 위치인 S번 서가는 이미 점검을 마쳤으므로 후보에서 제외한다. 도달할 수 없는 서가와 최소 도착 시간이 L분보다 큰 서가도 후보에서 제외한다. 서로 다른 후보 서가는 각각 한 번씩 센다. L이 0이면 통로를 지나 다른 서가에 도착할 시간이 없으므로 후보가 없다. 관리자는 후보의 전체 개수와 함께 마지막 점검 위치로 표시할 서가 하나를 알고 싶다. 마지막 위치는 후보 중 최소 도착 시간이 가장 큰 서가로 정한다. 그러한 서가가 여러 개라면 번호가 가장 작은 서가를 선택한다. 선택된 서가의 번호와 최소 도착 시간도 함께 구한다. 이 작업은 모든 후보를 한 번의 이동 경로로 방문하는 일정을 만드는 것이 아니다. 각 후보까지 따로 이동한다고 생각하고 최단 도착 시간을 비교한다. 후보가 하나도 없다면 개수는 0으로, 서가 번호와 도착 시간은 각각 -1로 표시한다.

입력

첫째 줄에 정수 N, M, S, L이 공백으로 주어진다. 1 ≤ N ≤ 12,000, 0 ≤ M ≤ min(24,000, N(N-1)/2), 1 ≤ S ≤ N, 0 ≤ L ≤ N-1이다.
다음 M개 줄에는 통로가 연결하는 두 서가 번호 u, v가 주어진다. u와 v는 1 이상 N 이하의 서로 다른 정수다. 같은 두 서가를 연결하는 통로는 중복하여 주어지지 않는다.

출력

후보 서가의 개수, 마지막 위치로 선택한 서가 번호, 그 서가의 최소 도착 시간을 한 줄에 공백으로 구분하여 출력한다. 후보가 없으면 0 -1 -1을 출력한다.

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

4 3 2

3 0 1 2

0 -1 -1

출처: Devin.KR 자체 제작