운동 뒤의 급수대

문제

한 헬스장은 여러 운동 구역을 통로로 연결해 운영한다. 운동 구역에는 1번부터 N번까지 번호가 붙어 있다. 각 통로는 서로 다른 두 구역을 직접 연결하며, 어느 방향으로든 지나갈 수 있다. 통로 하나를 지나는 데 걸리는 시간은 모두 같다. 서로 다른 통로를 연이어 지나 다른 구역으로 이동할 수 있지만, 통로로 연결되지 않은 구역 사이를 곧바로 이동할 수는 없다. 회원 한 명이 S번 구역에서 운동을 마쳤다. 회원은 물을 마시기 위해 급수대가 설치된 다른 구역으로 이동하려 한다. 각 구역에는 급수대가 하나 있거나 없으며, 급수대의 설치 여부는 입력으로 주어진다. S번 구역에 급수대가 있더라도 이번 이동의 목적지로는 선택하지 않는다. 회원이 운동을 마친 구역을 벗어나 다른 급수대를 이용하려 하기 때문이다. 회원은 지나야 하는 통로의 수가 가장 적은 급수대 구역을 선택한다. 어떤 구역까지 가는 이동 방법이 여러 개라면, 그중 통로를 가장 적게 지나는 방법으로 해당 구역까지의 거리를 정한다. 두 급수대 구역까지의 거리가 같으면 구역 번호가 더 작은 쪽을 선택한다. 이동 중에는 급수대가 없는 구역도 지나갈 수 있으며, 같은 구역이나 통로를 다시 지나는 것 자체가 금지되지는 않는다. 헬스장의 모든 구역이 하나로 이어져 있다고 보장되지는 않는다. 급수대가 설치되어 있어도 S번 구역에서 통로를 따라 도달할 수 없다면 선택할 수 없다. S번 구역 이외에 급수대가 전혀 없는 경우도 있다. 선택할 수 있는 급수대 구역이 있다면 그 구역 번호와 도달하기 위해 지나야 하는 최소 통로 수를 구한다. 선택할 수 있는 급수대 구역이 하나도 없다면 정해진 값 -1을 출력한다. 실제 이동 경로나 지나간 구역들의 목록은 출력하지 않는다.

입력

첫째 줄에 정수 N, M, S가 공백으로 주어진다. 1 ≤ N ≤ 10,000, 0 ≤ M ≤ 20,000, 1 ≤ S ≤ N이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 주어진다. 각 A_i는 0 또는 1이며, A_i = 1이면 i번 구역에 급수대가 있다.
다음 M개 줄에 통로의 양 끝 구역 번호 u, v가 주어진다. 1 ≤ u, v ≤ N이고 u ≠ v이다. 같은 두 구역을 연결하는 통로가 여러 번 주어질 수 있으며, 각각 하나의 통로로 취급한다. M = 0이면 통로 정보는 주어지지 않는다.

출력

선택할 급수대 구역이 있으면 구역 번호와 최소 통로 수를 공백으로 구분하여 한 줄에 출력한다. 최소 통로 수가 같은 후보가 여럿이면 번호가 가장 작은 구역을 출력한다. 선택할 수 있는 구역이 없으면 -1만 출력한다.

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

1 2

4 2 1
1 0 1 1
1 2
3 4

-1

1 0 1
1

-1

출처: Devin.KR 자체 제작