학원 비상구 최단 대피

문제

한 학원 건물에는 1번부터 N번까지 번호가 붙은 교실이 있고, 교실 사이에는 M개의 일방통행 복도가 있다. j번째 복도는 u_j번 교실에서 v_j번 교실로만 이동할 수 있으며, 한 복도를 지나는 데 걸리는 거리는 1이다. 같은 복도가 중복되어 주어지거나 u_j와 v_j가 같은 복도가 있을 수도 있다. 건물에는 K개의 비상구 교실이 있다. 비상구 교실에 있는 사람은 이미 대피한 것으로 보아 거리가 0이다. 또 B개의 교실은 공사 중이어서 그 교실에 들어가거나 통과하거나 그 교실에서 출발할 수 없다. 비상구 교실은 공사 중인 교실이 아니다. 각 교실에서 출발하여 복도를 따라 이동해 비상구 교실 중 어느 한 곳에 도달하는 최단 거리를 구하시오. 공사 중인 교실이거나, 공사 중이 아닌 교실만 거쳐서는 어떤 비상구에도 도달할 수 없는 교실의 값은 -1로 한다. 교실이 많고 복도도 많으므로 교실마다 따로 탐색하지 않고 효율적인 방법을 써야 한다.

입력

첫 줄에 네 정수 N, M, K, B가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ M ≤ 200,000, 1 ≤ K ≤ N, 0 ≤ B ≤ N-K) 둘째 줄에 서로 다른 비상구 교실 번호 K개가 주어진다. 셋째 줄에 서로 다른 공사 중인 교실 번호 B개가 주어진다. B가 0이면 셋째 줄은 비어 있다. 이어서 M개의 줄에 u_j, v_j가 공백으로 구분되어 주어진다. (1 ≤ u_j, v_j ≤ N) 비상구와 공사 중인 교실은 서로 겹치지 않는다.

출력

1번 교실부터 N번 교실까지 순서대로 최단 거리를 공백으로 구분하여 한 줄에 출력한다.

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

2 1 -1 -1 -1 0

4 3 2 0
1 4

2 1
3 2
3 4

0 1 1 0

출처: Devin.KR 자체 제작