Laiko ribojimas: 2s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Paieška platyn

Jums duotas jungus grafas, sudarytas iš n (1\\leqn\\leq10^5) viršūnių ir m (n-1\\leqm\\leq2*10^5) briaunų. Kiekvienai viršūnei suraskite trumpiausią atstumą nuo jos iki 1-osios viršūnės.

Įvestis

Pirmoje eilutėje pateikti du tarpais atskirti skaičiai n ir m. Kitose m eilučių pateikta po 2 skaičius a_i ir b_i. Tai reiškia, jog tarp a_i ir b_i viršūnių grafe yra briauna.

Rezultatai

Išveskite n skaičių c_1,c_2,...,c_n. Čia c_i yra trumpiausias atstumas nuo viršūnės 1 iki viršūnės i. Atstumas tarp dviejų viršūnių - briaunų kiekis kelyje tarp šių viršūnių.

Pavyzdžiai

Duomenys Rezultatai Paaiškinimas
5 5
3 5
2 4
3 4
1 5
1 3
0 3 1 2 1