Problem
One of the Top-Secret Organizations, whose name we are not allowed to reveal, is a network of
N underground bunkers connected by tunnels of equal length, through which one can get from any bunker to any other (not necessarily directly). Communication with the outside world is carried out through special secret exits, which are located in some of the bunkers.
The organization needed to draw up a staff evacuation plan in case of an emergency. To do this, for each of the bunkers, you need to find out how long it will take to get to the nearest exit. You, as a specialist in such tasks, are instructed to calculate the required time for each of the bunkers according to a given description of the premises of the Top Secret Organization. For your convenience, the bunkers are numbered from
1 to
N.
Input:
- the first two lines contain two natural numbers
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — the number of bunkers and the number of exits respectively;
- in the third line, space-separated
K different numbers from
1 to
N, indicating the numbers of the bunkers where the exits are located;
- the fourth line contains the number
M (
\(1 <= M <= 100000\)) — number of tunnels;
- in the following
M lines enter pairs of numbers – numbers of bunkers connected by a tunnel.
Each of the tunnels can move in both directions. An organization does not have tunnels leading from a bunker to itself, but there can be more than one tunnel between a pair of bunkers.
Output: print
N space-separated numbers — for each of the bunkers, the minimum time required to get to the exit. Assume that the time to travel through one tunnel is
1.
Examples
| # |
Input |
Output |
| 1 |
3
1
2
3
1 2
3 1
2 3
| 1 0 1 |
| 2 |
10
2
10 8
9
67
75
58
8 1
1 10
10 3
34
49
9 2 |
1 4 1 2 1 3 2 0 3 0 |