회의실 장비 지원 구역

문제

여러 회의실이 있는 교육동에서 이동식 발표 장비를 배치하려고 한다. 회의실에는 1번부터 N번까지 번호가 붙어 있으며, 일부 회의실 쌍은 내부 통로로 직접 연결되어 있다. 모든 통로는 양방향으로 이동할 수 있고, 통로 하나를 지나는 데 걸리는 시간은 모두 같다. 건물 바깥으로 나가 다른 회의실로 이동하는 것은 허용하지 않는다. 관리자는 서로 다른 K개 회의실을 장비 보관실로 지정했다. 각 회의실에서 장비를 요청하면 가장 가까운 보관실이 지원하도록 담당 구역을 미리 정하려고 한다. 두 회의실 사이의 거리는 한쪽에서 다른 쪽으로 이동할 때 지나야 하는 통로 수의 최솟값이다. 이동할 수 있는 경로가 없으면 두 회의실 사이의 거리는 정해지지 않는다. 같은 회의실 사이의 거리는 0이므로 보관실은 항상 자기 자신을 담당 보관실로 선택한다. 어떤 회의실에서 도달할 수 있는 보관실이 여러 개라면 그중 거리가 가장 짧은 보관실을 선택한다. 최단 거리가 같은 보관실이 여러 개라면 회의실 번호가 가장 작은 보관실을 선택한다. 보관실 번호가 입력된 순서는 우선순위와 관계없다. 도달할 수 있는 보관실이 하나도 없는 회의실은 지원 불가로 표시한다. 통로 목록에는 같은 두 회의실을 연결하는 정보가 여러 번 등장할 수 있고, 어떤 회의실에서 자기 자신으로 이어지는 통로가 등장할 수도 있다. 이 정보들도 그대로 주어지며, 통로를 지날 때마다 이동 횟수는 1 증가한다. 이러한 통로가 있어도 거리와 담당 보관실을 정하는 규칙은 같다. 모든 회의실에 대해 가장 가까운 보관실까지의 거리와 최종 담당 보관실 번호를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄에 서로 다른 K개의 보관실 번호가 공백으로 구분되어 주어진다. 다음 M개 줄에는 통로 양 끝의 회의실 번호인 정수 u와 v가 주어진다. 1 ≤ N ≤ 10,000, 0 ≤ M ≤ 20,000, 1 ≤ K ≤ N이며, 모든 회의실 번호는 1 이상 N 이하이다. 중복 통로와 u = v인 통로가 허용된다.

출력

회의실 번호 1부터 N까지 순서대로 N개 줄을 출력한다. 보관실에 도달할 수 있으면 가장 가까운 보관실까지의 거리와 담당 보관실 번호를 공백으로 구분하여 출력한다. 도달할 수 있는 보관실이 없으면 -1 -1을 출력한다.

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

0 1
1 1
2 1
1 5
0 5
-1 -1

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

1 2
0 2
1 4
0 4

1 0 1
1

0 1

출처: Devin.KR 자체 제작