COCI '19 Contest 6 #2 Birmingham

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

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 in 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.

Input

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 in 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_i and B_i (1 \le A_i, B_i \le N, A_i \ne B_i), which denote that the i-th road connects houses with indices A_i and B_i.

Output

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

Scoring

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.

Sample Input 1

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

Sample Output 1

1 1 2 2 1 0

Sample Input 2

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

Sample Output 2

1 1 1 0 1 0

Sample Input 3

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

Sample Output 3

1 1 1 2 1 0

Explanation of Sample Output 3

The figure represents a graph from the third example. Since houses 1, 2, 3 and 5 are at most two steps away from house 6, people living in them will find out about the winner the day after the meeting. Person living in house 4 will find out about the winner two days after the meeting.


Comments


  • 3
    TypicalToxic  commented on Aug. 22, 2020, 5:40 p.m.

    For Sample Input 1, How does house 4 receive the score on the second day?

    Isn't it,

    6 - > 1 - > 3 -> 4

    House 4 receives the news on the third day?

    What am I missing?


    • 1
      d  commented on Aug. 23, 2020, 3:30 a.m.

      In the first meeting, house 6 sends the score to house 1.

      In the second meeting, house 1 sends the score to house 4.