Un mesaj trebuie să ajungă de la cel mai important sat al elfilor la toate celelalte sate.
În prima zi, câte un elf pleacă din acest sat către fiecare dintre satele care sunt legate direct de satul respectiv. Călătoria unui elf durează o zi. În a doua zi, toate satele care au primit mesajul îl trimit, prin intermediul unui elf, spre satele învecinate. Din nou, călătoria durează o zi. Practic, orice sat, în ziua în care primește pentru prima dată mesajul, îl trimite spre toate satele învecinate. Este posibil ca un sat să primească de mai multe ori mesajul. În această situație mesajul se va trimite spre satele învecinate doar prima dată. Cunoscând harta regiunii, elfii din cel mai important sat ar dori să știe, pentru fiecare sat în parte, care este numărul minim de zile după care satul respectiv va primi mesajul. Există n sate ale elfilor care sunt identificate prin numere cuprinse între 1 și n, iar cel mai important sat este identificat prin 1.
Prima linie a fișierului de intrare INPUT.TXT conține numărul n al satelor elfilor.
Cea de-a doua linie a fișierului conține numărul total m al cărărilor care leagă satele elfilor. Fiecare dintre următoarele m linii conține câte două numere întregi, separate printr-un spațiu, care indică două sate care sunt legate direct printr-o cărare.
Fișierul de ieșire OUTPUT.TXT trebuie să conțină n - 1 linii pe care se va afla câte un număr.
Fiecare dintre aceste linii va conține numărul de zile necesar pentru ca mesajul să ajungă la unul dintre sate (cu excepția celui mai important). Ordinea liniilor este dată de numerele de ordine ale satelor elfilor.
INPUT.TXT
4 5 1 2 1 3 2 3 2 4 3 4 OUTPUT.TXT 1 1 2
|