Problem
Uma das organizações ultra-secretas, cujo nome não podemos revelar, é uma rede de
N bunkers subterrâneos conectados por túneis de igual comprimento, através dos quais se pode ir de qualquer bunker para qualquer outro ( não necessariamente diretamente). A comunicação com o mundo exterior é feita através de saídas secretas especiais, localizadas em alguns dos bunkers.
A organização precisava elaborar um plano de evacuação de funcionários em caso de emergência. Para fazer isso, para cada um dos bunkers, você precisa descobrir quanto tempo levará para chegar à saída mais próxima. Você, como especialista nessas tarefas, é instruído a calcular o tempo necessário para cada um dos bunkers de acordo com uma determinada descrição das instalações da Organização Top Secret. Para sua conveniência, os bunkers são numerados de
1 a
N.
Entrada:
- as duas primeiras linhas contêm dois números naturais
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — o número de bunkers e o número de saídas respectivamente;
- na terceira linha,
K separados por espaços, números diferentes de
1 a
N, indicando os números dos bunkers onde se encontram as saídas;
- a quarta linha contém o número
M (
\(1 <= M <= 100000\)) — número de túneis;
- no seguinte
M linhas inserem pares de números – números de bunkers conectados por um túnel.
Cada um dos túneis pode se mover em ambas as direções. Uma organização não possui túneis levando de um bunker até ela mesma, mas pode haver mais de um túnel entre um par de bunkers.
Saída: imprime
N números separados por espaços — para cada um dos bunkers, o tempo mínimo necessário para chegar à saída. Suponha que o tempo para viajar por um túnel seja
1.
Exemplos
| # |
Entrada |
Saída |
| 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 |