It is well known that all horse races in Birmingham are fixed days in advance.
It is a little less known that people who fix these races (and thereby know
the winner) do that on a secret meeting and start spreading the information
around the city the day after that meeting.
The first day after the meeting, all people that know the information about
the winner start sharing that information with all people that live at most
\(K\) steps away from their house.
The second day after the meeting, all people that know the information about the winner start sharing
that information with all people that live at most \(2 \cdot K\) steps away from their house.
In general, \(X-th\) day after the meeting, all people that know the information about the winner start
sharing that information with all people that live at most \(X \cdot K\) steps away from their house.
We can represent Birmingham as a graph where vertices represent the houses and edges represent
bidirectional roads which connect these houses. Houses are indexed with increasing integers from 1 to \(N\)
and we say that a person can travel each road in a single step. It is possible to reach each house from
each other house by traversing a sequence of roads.
Your task is to determine, for each house, on which day will the information about the race winner reach
it.

In the test cases worth a total of 20 points, it will hold \(K = 1\), \(1 \le N\), \(Q \le 100\) and \(1 \le M \le 200\).
In the test cases worth an additional 15 points, it will hold \(1 \le N\), \(Q \le 100\) and \(1 \le M \le 200\).

The first line contains four integers \(N\), \(M\), \(Q\) and \(K\) (\(1 \le N\), Q, \(K \le 100\,000\), \(Q \le N\), \(1 \le M \le 200\,000\)),
the number of houses in Birmingham, the number of roads in Birmingham, the number of people that
were present on the secret meeting and the number \(K\) from task description.
The next line contains \(Q\) integers where the \(i-th\) integer represents the index of a house where the \(i-th\)
person from the secret meeting lives in.
The \(i-th\) of the next \(M\) lines contains integers \(A@@RISE_MATH_BLOCK_0@@i\) (\(1 \le A@@RISE_MATH_BLOCK_1@@i\)), which denote that
the \(i-th\) road connects houses with indices \(A_{i}\) and \(B_{i}\).

Output \(N\) numbers where the \(i-th\) number represents on which day after the meeting will the person
living in house with index \(i\) find out who will win the race. If the person living in that house was present
on the secret meeting, output 0 instead.

생성자가 기록되지 않았습니다.

출처 COCI 2019/2020 Contest 6