고장 난 작업대를 피하는 컨베이어 경로

문제

공장 생산 라인에는 1번부터 N번까지 번호가 붙은 작업대 N개가 있다. 작업대 사이에는 한 방향으로만 움직이는 컨베이어가 M개 놓여 있으며, j번째 컨베이어는 u_j번 작업대에서 v_j번 작업대로 부품을 옮긴다. 같은 쌍을 잇는 컨베이어가 여러 개이거나 자기 자신으로 돌아오는 컨베이어가 있을 수도 있다. 원자재는 항상 1번 작업대에 투입되고, 완제품은 N번 작업대에서 나온다. 오늘은 고장 난 작업대가 K개 있다. 고장 난 작업대에는 부품이 들어갈 수 없으므로 투입, 반출, 경유 모두 불가능하다. 따라서 1번이나 N번이 고장이면 그 작업대는 쓸 수 없다. 부품이 지나는 컨베이어의 수를 경로의 길이라고 한다. 고장 나지 않은 작업대만 거쳐 1번에서 N번까지 가는 경로 중 길이가 가장 짧은 값을 구하고, 함께 1번에서 고장 난 작업대를 거치지 않고 도달할 수 있는 작업대가 모두 몇 개인지 구하시오. 1번 작업대 자신도 고장이 아니라면 도달 가능한 작업대로 센다. N이 1이고 1번이 고장이 아니면 최단 길이는 0이다. 1번에서 N번으로 갈 수 없으면 최단 길이 자리에 -1을 출력한다.

입력

첫 줄에 정수 N, M, K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ M ≤ 200,000, 0 ≤ K ≤ N) 둘째 줄에 고장 난 작업대 번호 K개가 서로 다르게 공백으로 구분되어 주어진다. K가 0이면 이 줄은 비어 있다. 이어지는 M개의 줄에 각각 u_j, v_j가 공백으로 구분되어 주어진다. (1 ≤ u_j, v_j ≤ N)

출력

한 줄에 최단 길이와 도달 가능한 작업대의 수를 공백으로 구분하여 출력한다.

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

4 5

4 3 1
2
1 2
2 4
3 4

-1 1

3 2 1
1
1 2
2 3

-1 0

출처: Devin.KR 자체 제작