가장 먼 급수 지점 점검

문제

마라톤 대회 운영팀은 대회가 시작되기 전에 급수 지점의 준비 상태를 점검한다. 대회 구역에는 번호가 붙은 여러 지점이 있고, 일부 지점 사이에는 운영 요원이 걸어서 이동할 수 있는 통로가 있다. 각 통로는 양쪽 방향으로 이용할 수 있다. 모든 통로를 지나는 데 걸리는 시간은 똑같이 1분이며, 지점에서 머무는 시간은 계산하지 않는다. 점검 요원은 출발 지점 S에서 이동을 시작한다. 운영팀은 출발 지점에서 가장 멀리 있는 급수 지점을 먼저 점검 대상으로 지정하려고 한다. 여기서 어떤 지점까지의 거리는 출발 지점에서 그곳까지 이동할 때 지나야 하는 통로 수의 최솟값이다. 일부러 돌아가는 경로를 이용하여 거리를 늘릴 수는 없다. 통로가 복잡하게 연결되어 있더라도 가능한 이동 경로 중 통로 수가 가장 적은 경로를 기준으로 한다. 출발 지점에서 도달할 수 없는 급수 지점은 점검 대상에서 제외한다. 도달할 수 있는 급수 지점 중 거리가 가장 큰 지점을 선택하며, 그 거리가 같은 급수 지점이 여러 개라면 지점 번호가 가장 작은 곳을 선택한다. 선택한 지점의 번호와 그곳까지의 거리를 보고해야 한다. 급수 지점이 아닌 곳은 다른 지점으로 이동하기 위해 지나갈 수 있지만, 최종 점검 대상으로 선택할 수는 없다. 출발 지점 자체가 급수 지점일 수도 있다. 이 경우 출발 지점까지의 거리는 0이다. 출발 지점 이외의 급수 지점에 도달할 수 없다면 출발 지점이 선택될 수 있다. 한편 급수 지점이 하나도 없거나, 모든 급수 지점이 출발 지점과 끊어져 있다면 선택 가능한 지점이 없다. 주어진 통로와 급수 지점 정보를 바탕으로 운영팀이 보고할 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, S가 공백으로 구분되어 주어진다. N은 지점 수로 1 이상 20,000 이하이고, M은 통로 수로 0 이상 min(28,000, N(N-1)/2) 이하이며, S는 1 이상 N 이하다.
둘째 줄에 길이가 N인 문자열이 주어진다. i번째 문자가 1이면 i번 지점은 급수 지점이며, 0이면 급수 지점이 아니다.
다음 M개 줄에 통로 양 끝의 지점 번호 u, v가 주어진다. u와 v는 1 이상 N 이하의 서로 다른 정수다. 같은 두 지점을 연결하는 통로는 중복해서 주어지지 않는다.

출력

선택한 지점 번호와 출발 지점에서의 거리를 공백으로 구분하여 출력한다. 선택 가능한 지점이 없으면 -1만 출력한다.

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

5 3

4 1 1
0011
1 2

-1

1 0 1
1

1 0

출처: Devin.KR 자체 제작