탈출 계획

기업 전력 회사 사무실에서 혁신적인 발전소의 설계도가 도난당했습니다. 이 발전소가 지어진다면 현대 에너지 문제의 대부분을 해결하고, 당신을 엄청난 부자로 만들어 줄 것입니다. 하지만 아직 절망할 필요는 없습니다. 보안팀이 도둑을 추적해 설계도가 경쟁사가 소유한 지하 벙커에 보관되어 있다는 사실을 알아냈습니다. 가장 유능한 요원이 이미 설계도를 되찾으러 떠났지만, 임무는 매우 어렵습니다!

경쟁사 시스템에는 아직 Heartbleed 취약점이 남아 있습니다. 덕분에 IT 부서는 벙커 보안 시스템에 제한된 접근 권한을 얻었고, 벙커의 평면도를 찾아냈습니다. 벙커는 $N$개의 방과 이를 연결하는 $M$개의 복도로 이루어져 있습니다. 모든 복도는 양방향으로 지나갈 수 있습니다. 어떤 복도도 방을 자기 자신과 잇지 않으며, 두 방을 잇는 복도는 최대 하나입니다(이렇게 외에 복도를 만들 이유가 없지 않습니까?).

일부 방에는 벙커의 출구가 있습니다. 요원이 설계도를 집으면 그 방에서 경보가 울립니다. 그러면 모든 출구가 닫히고 요원은 갇히게 됩니다.

CTF 대회로 단련된 우리 IT 팀은 보안 시스템을 바꿨습니다. 이제 방 $i$에서 경보가 울리면 모든 출구가 닫히지 않고, 그 방에서 가장 가까운 $K$개의 출구만 닫힙니다. 두 방 사이의 거리는 한 방에서 다른 방으로 가기 위해 지나야 하는 복도의 최소 개수입니다. 방 $i$에서 같은 거리에 있는 출구는 방 번호가 작은 순서대로 닫힙니다.

첫 줄에 공백으로 구분된 정수 $N$과 $M$이 주어집니다. 각각 방의 개수와 복도의 개수입니다($1 \le N \le 100000$, $0 \le M \le 100000$). 이어지는 $M$개의 줄에는 각각 $a_i$와 $b_i$가 주어지며, 이는 $i$번째 복도가 연결하는 방 번호입니다($1 \le a_i, b_i \le N$). 다음 줄에는 출구가 있는 방의 개수 $A$가 주어집니다($1 \le A \le N$). 그다음 줄에는 출구가 있는 방 번호 $e_i$가 공백으로 구분되어 주어집니다($1 \le e_i \le N$). 이 번호들은 서로 다릅니다. 마지막 줄에는 경보 시 닫히는 출구의 개수 $K$가 주어집니다($0 \le K \le 10$).

$N$개의 정수를 출력합니다. $i$번째 정수는 방 $i$에서 경보가 울린 뒤 가장 가까운 열린 출구가 있는 방의 번호입니다. 거리가 같은 방이 여럿이면 방 번호가 가장 작은 방을 고릅니다. 방 $i$에서 탈출할 수 없다면 -1을 출력합니다.

첫 번째 예제에서는 $K = 0$이므로 각 방에서 가장 가까운 출구만 찾으면 됩니다. 방 2를 제외한 모든 답은 하나로 정해집니다. 방 1과 방 3에는 각각 통로 한 칸 거리에 출구가 있고, 둘 중 방 번호가 작은 1이 답입니다.

두 번째 예제에서 방 6부터 9까지는 탈출할 수 없습니다. 이 방들에서 도달할 수 있는 출구는 두 개뿐이고, 경보가 울리면 둘 다 닫히기 때문입니다.