Problem
Una de las Organizaciones Top-Secret, cuyo nombre no podemos revelar, es una red de
N bunkers subterráneos conectados por túneles de igual longitud, a través de los cuales se puede ir de cualquier bunker a cualquier otro ( no necesariamente directamente). La comunicación con el mundo exterior se realiza a través de salidas secretas especiales, que se encuentran en algunos de los búnkeres.
La organización necesitaba elaborar un plan de evacuación del personal en caso de emergencia. Para hacer esto, para cada uno de los bunkers, debe averiguar cuánto tiempo llevará llegar a la salida más cercana. A usted, como especialista en tales tareas, se le indica que calcule el tiempo requerido para cada uno de los bunkers de acuerdo con una descripción dada de las instalaciones de la Organización Top Secret. Para su comodidad, los bunkers están numerados del
1 al
N.
Entrada:
- las dos primeras líneas contienen dos números naturales
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — el número de bunkers y el número de salidas respectivamente;
- en la tercera línea,
K, separados por espacios, números diferentes del
1 al
N, indicando los números de los bunkers donde se encuentran las salidas;
- la cuarta línea contiene el número
M (
\(1 <= M <= 100000\)) — número de túneles;
- en el siguiente
M las líneas ingresan pares de números – número de búnkeres conectados por un túnel.
Cada uno de los túneles puede moverse en ambas direcciones. Una organización no tiene túneles que vayan de un búnker a sí misma, pero puede haber más de un túnel entre un par de búnkeres.
Salida: imprime
N números separados por espacios — para cada uno de los bunkers, el tiempo mínimo necesario para llegar a la salida. Suponga que el tiempo para viajar a través de un túnel es
1.
Ejemplos
| # |
Entrada |
Salida |
| 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 |