Se da un graf neorientat simplu cu n noduri si m muchii, si o multime S de k noduri sursa. Determinati, pentru fiecare nod, distanta minima pana la cel mai apropiat nod din S.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii cu cate o muchie. Urmeaza o linie cu k, apoi o linie cu cele k noduri din S.
- Date de iesire
- Se afiseaza n numere separate prin spatiu: distanta minima de la nodul 1, 2, ..., n pana la cel mai apropiat nod din S (-1 daca niciun nod din S nu este accesibil).
- Restrictii
- 1 <= n <= 100000, 0 <= m <= 200000, 1 <= k <= n
Exemple
Exemplul 1
Intrare
6 5 1 2 2 3 3 4 4 5 5 6 2 1 6
Iesire
0 1 2 2 1 0
Exemplul 2
Intrare
5 4 1 2 2 3 3 4 4 5 1 3
Iesire
2 1 0 1 2