버밍엄
시간 제한1초메모리 제한512 MB
연결된 그래프와 Q개의 시작 집이 주어질 때, 각 집이 어떤 시작 집에서 X*K 간선 이내에 있는 가장 작은 날 X를 구한다.
문제
버밍엄의 모든 경마 경기는 며칠 전에 미리 조작된다는 사실은 잘 알려져 있다. 이 경기를 조작하는 사람들, 즉 우승자를 미리 아는 사람들이 비밀 회의에서 이를 결정하고, 회의 다음 날부터 도시 전체에 정보를 퍼뜨린다는 사실은 덜 알려져 있다.
회의 다음 날, 우승자 정보를 아는 모든 사람은 자신의 집에서 K걸음 이내에 사는 모든 사람에게 정보를 공유하기 시작한다.
회의 이틀째 날, 우승자 정보를 아는 모든 사람은 자신의 집에서 2 · K걸음 이내에 사는 모든 사람에게 정보를 공유하기 시작한다.
일반적으로, 회의로부터 X일째 날에는 우승자 정보를 아는 모든 사람이 자신의 집에서 X · K걸음 이내에 사는 모든 사람에게 정보를 공유하기 시작한다.
버밍엄은 정점이 집을 나타내고 간선이 집을 연결하는 양방향 도로를 나타내는 그래프로 표현할 수 있다. 집은 1부터 N까지의 증가하는 정수로 번호가 매겨지며, 사람은 각 도로를 한 걸음으로 이동할 수 있다. 어떤 집에서든 도로를 따라 이동하면 다른 모든 집에 도달할 수 있다.
각 집에 대해 경마 우승자 정보가 언제 도달하는지 구하는 것이 과제이다.
입력
첫째 줄에 네 정수 N, M, Q, K가 주어진다. (1 ≤ N, Q, K ≤ 100 000, Q ≤ N, 1 ≤ M ≤ 200 000) N은 버밍엄의 집 수, M은 도로 수, Q는 비밀 회의에 참석한 사람 수, K는 문제 설명에 나오는 수이다.
다음 줄에는 Q개의 정수가 주어지며, i번째 정수는 비밀 회의에 참석한 i번째 사람이 사는 집의 번호이다.
다음 M개의 줄 중 i번째 줄에는 정수 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi) 이는 i번째 도로가 번호 Ai와 Bi인 집을 연결한다는 뜻이다.
출력
N개의 수를 출력한다. i번째 수는 번호 i인 집에 사는 사람이 경마 우승자 정보를 언제 알게 되는지를 나타낸다. 만약 그 집에 사는 사람이 비밀 회의에 참석했다면 대신 0을 출력한다.