Escape Plan

The blueprints for an innovative power plant were stolen from the office of your energy corporation. If the plant were built, it would solve most problems of modern energy and make you incredibly rich. Do not despair yet. The security service tracked the thief and found that the blueprints are now kept in an underground bunker owned by a competitor. Your best agent has already set out to steal the blueprints back, but the mission is very hard!

The competitor's system still has the Heartbleed vulnerability, so your IT department got limited access to the bunker's security system and found its floor plan. The bunker has $N$ rooms and $M$ corridors connecting them. Every corridor can be walked in both directions. No corridor connects a room to itself, and no two rooms are connected by more than one corridor (who would build corridors any other way?).

Some rooms contain exits from the bunker. As soon as an agent takes the blueprints, the alarm goes off in the room where the agent is. After that, all exits close and the agent is trapped.

Our IT team, toughened by CTF competitions, changed the security system so that when the alarm goes off in room $i$, not all exits close, only the $K$ closest to that room. The distance between two rooms is the minimum number of corridors that must be traversed to get from one to the other. Exits at the same distance from room $i$ close in increasing order of their room numbers.

The first line contains two space-separated integers $N$ and $M$, the number of rooms and corridors ($1 \le N \le 100000$, $0 \le M \le 100000$). Each of the next $M$ lines contains two integers $a_i$ and $b_i$, the rooms connected by the $i$-th corridor ($1 \le a_i, b_i \le N$). The next line contains $A$, the number of rooms with exits ($1 \le A \le N$). The next line contains $A$ distinct space-separated integers $e_i$, the rooms with exits ($1 \le e_i \le N$). The last line contains $K$, the number of exits closed by the alarm ($0 \le K \le 10$).

Print $N$ integers. The $i$-th integer is the number of the nearest room with an open exit after the alarm goes off in room $i$. If several suitable rooms are equally close, choose the one with the smallest number. If room $i$ offers no escape, print -1.

In the first example $K = 0$, so each room just needs its nearest exit. The answer is unique for every room except room 2. Rooms 1 and 3 each have an exit one corridor away, so the answer is the smaller number, room 1.

In the second example, rooms 6 through 9 cannot escape. Only two exits are reachable from them, and the alarm closes both.