Problem
Una delle Organizzazioni Top-Secret, il cui nome non ci è permesso rivelare, è una rete di
N bunker sotterranei collegati da tunnel di uguale lunghezza, attraverso i quali si può passare da qualsiasi bunker a qualsiasi altro ( non necessariamente direttamente). La comunicazione con il mondo esterno avviene tramite speciali uscite segrete, che si trovano in alcuni bunker.
L'organizzazione doveva redigere un piano di evacuazione del personale in caso di emergenza. Per fare ciò, per ciascuno dei bunker, devi scoprire quanto tempo ci vorrà per raggiungere l'uscita più vicina. Tu, in qualità di specialista in tali compiti, sei incaricato di calcolare il tempo necessario per ciascuno dei bunker secondo una data descrizione dei locali dell'Organizzazione Top Secret. Per comodità, i bunker sono numerati da
1 a
N.
Input:
- le prime due righe contengono due numeri naturali
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — rispettivamente il numero di bunker e il numero di uscite;
- nella terza riga,
K separati da spazi numeri diversi da
1 a
N, indicanti i numeri dei bunker dove sono ubicate le uscite;
- la quarta riga contiene il numero
M (
\(1 <= M <= 100000\)) — numero di tunnel;
- nella seguente
M le linee inseriscono coppie di numeri – numero di bunker collegati da un tunnel.
Ciascuno dei tunnel può muoversi in entrambe le direzioni. Un'organizzazione non ha tunnel che portano da un bunker a se stessa, ma può esserci più di un tunnel tra una coppia di bunker.
Output: stampa
N numeri separati da spazio — per ciascuno dei bunker, il tempo minimo necessario per raggiungere l'uscita. Supponiamo che il tempo necessario per attraversare un tunnel sia
1.
Esempi
| # |
Input |
Uscita |
| 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 |