Problem
L'une des Organisations Top-Secrètes, dont nous ne sommes pas autorisés à révéler le nom, est un réseau de bunkers souterrains
N reliés par des tunnels d'égale longueur, à travers lesquels on peut passer de n'importe quel bunker à n'importe quel autre ( pas nécessairement directement). La communication avec le monde extérieur s'effectue par des sorties secrètes spéciales, situées dans certains bunkers.
L'organisation devait établir un plan d'évacuation du personnel en cas d'urgence. Pour ce faire, pour chacun des bunkers, vous devez savoir combien de temps il vous faudra pour vous rendre à la sortie la plus proche. En tant que spécialiste de ces tâches, vous êtes chargé de calculer le temps requis pour chacun des bunkers en fonction d'une description donnée des locaux de l'organisation Top Secret. Pour votre commodité, les bunkers sont numérotés de
1 à
N.
Entrée :
- les deux premières lignes contiennent deux nombres naturels
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — le nombre de bunkers et le nombre de sorties respectivement ;
- en troisième ligne, des
K séparés par des espaces, des chiffres différents de
1 à
N, indiquant les numéros des bunkers où se trouvent les sorties ;
- la quatrième ligne contient le nombre
M (
\(1 <= M <= 100000\)) — nombre de tunnels ;
- dans le
M les lignes entrent des paires de nombres – nombre de bunkers reliés par un tunnel.
Chacun des tunnels peut se déplacer dans les deux sens. Une organisation n'a pas de tunnels menant d'un bunker à elle-même, mais il peut y avoir plus d'un tunnel entre une paire de bunkers.
Sortie : imprimer
N nombres séparés par des espaces — pour chacun des bunkers, le temps minimum nécessaire pour se rendre à la sortie. Supposons que le temps nécessaire pour traverser un tunnel est de
1.
Exemples
| # |
Entrée |
Sortie |
| 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 |