ŠIOM — Paieška platyn

Laiko ribojimas: 2s

Atminties ribojimas: 64MB

Language:
Source file:
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

Šeštadieninė informatikos olimpiadininkų mokykla

Paieška platyn

Įvestis

Rezultatai

Pavyzdžiai