우체국의 마지막 전달 구역

문제

한 우체국은 담당 지역을 N개의 전달 구역으로 나누고, 각 구역에 1번부터 N번까지 번호를 붙였다. 우편물 분류 기준이 바뀌어 모든 구역에 새 안내문을 전달해야 한다. 안내문은 처음에 S번 구역에만 있으며, 구역 사이에 미리 정해진 연락 통로를 이용하여 다른 구역으로 전달할 수 있다. 연락 통로 하나는 서로 다른 두 구역을 연결한다. 통로는 어느 방향으로든 사용할 수 있으며, 한 통로를 거쳐 안내문을 전달하는 데에는 정확히 1분이 걸린다. 두 구역 사이에 직접 통로가 없다면 다른 구역을 거쳐야 한다. 모든 구역이 서로 연결되어 있다는 보장은 없으므로, S번 구역에서 어떤 방법으로도 안내문을 받을 수 없는 구역이 있을 수 있다. 전달은 시각 0에 시작한다. S번 구역은 시각 0에 이미 안내문을 받은 것으로 본다. 안내문을 받은 구역은 그 내용을 복사하여 연결된 모든 이웃 구역에 동시에 전달할 수 있다. 복사에 걸리는 시간은 없으며, 한 구역이 여러 이웃에 전달하더라도 각 전달은 서로를 지연시키지 않는다. 여러 경로로 안내문이 도착하면 가장 먼저 도착한 시각만 그 구역의 수신 시각으로 사용한다. 우체국은 전달 결과를 세 정수로 요약하려 한다. 첫 번째는 안내문을 끝내 받지 못하는 구역의 수이다. 두 번째는 안내문을 받을 수 있는 구역들 중 가장 늦은 수신 시각이다. 세 번째는 그 시각에 처음 안내문을 받는 구역들 중 번호가 가장 작은 구역의 번호이다. 안내문을 받지 못하는 구역은 두 번째와 세 번째 값을 정할 때 제외한다. S번 구역은 항상 안내문을 받으므로 가장 늦은 수신 시각과 해당 구역 번호는 언제나 정할 수 있다. S번 구역 외에 아무 구역도 안내문을 받지 못한다면 가장 늦은 수신 시각은 0이고 선택할 구역 번호는 S이다. 주어진 연락 통로를 이용하여 이 세 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, S가 공백으로 구분되어 주어진다. 1≤N≤200,000, 0≤M≤min(20,000,N(N-1)/2), 1≤S≤N이다.
다음 M개 줄에 연락 통로로 연결된 두 구역의 번호 U, V가 공백으로 구분되어 주어진다. 1≤U,V≤N이며 U≠V이다. 같은 두 구역을 연결하는 통로가 중복해서 주어지지 않는다.

출력

안내문을 받지 못하는 구역 수, 가장 늦은 수신 시각, 그 시각에 안내문을 받는 구역 중 가장 작은 번호를 공백으로 구분하여 한 줄에 출력한다.

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

1 3 6

6 4 2
2 4
2 5
4 1
5 3

1 2 1

4 0 3

3 0 3

출처: Devin.KR 자체 제작