안전한 부품 운반 경로

문제

어느 공장의 생산 라인에는 1번부터 N번까지 번호가 붙은 작업장 N개가 있고, 작업장 사이를 잇는 양방향 컨베이어 M개가 있다. 컨베이어를 따라가면 모든 작업장에서 다른 모든 작업장으로 갈 수 있다. 같은 두 작업장을 잇는 컨베이어가 여러 개 있을 수 있지만, 자기 자신을 잇는 컨베이어는 없다. N개의 작업장 중 K개에는 소화 설비가 설치되어 있다. 각 작업장의 안전 거리는 그 작업장에서 소화 설비가 있는 작업장 중 가장 가까운 곳까지 가는 데 필요한 최소 컨베이어 수로 정의한다. 소화 설비가 있는 작업장의 안전 거리는 0이다. 부품 상자를 1번 작업장에서 N번 작업장까지 컨베이어를 따라 옮기려 한다. 1번과 N번은 서로 다른 작업장이다. 한 경로의 안전도는 그 경로가 지나는 모든 작업장(출발점 1번과 도착점 N번도 포함)의 안전 거리 중 최솟값이다. 같은 작업장이나 컨베이어를 여러 번 지나도 되며, 안전도가 같은 경로는 어느 것을 골라도 상관없다. 1번 또는 N번에 소화 설비가 있으면 그 경로의 안전도는 0 이하가 되므로 답은 0이다. 1번에서 N번까지 가는 모든 경로 중 안전도의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N, M, K 가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000, 1 ≤ K ≤ N)
둘째 줄에 소화 설비가 있는 서로 다른 작업장 번호 K개가 공백으로 구분되어 주어진다.
이어지는 M개의 줄에 컨베이어가 잇는 두 작업장 번호 u, v 가 주어진다. (1 ≤ u, v ≤ N, u ≠ v)

출력

안전도의 최댓값을 한 줄에 출력한다.

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

2

3 2 2
1 3
1 2
2 3

0

출처: Devin.KR 자체 제작