Masalalar
#028
~/algor $ cat masalalar/eng-qisqa-yol
Eng qisqa yo'l
O'rtacha
2000 ms
128 MB
45%
Mavzular:
Graf va daraxtlar
Shaharda n ta chorraha va m ta ikki tomonlama ko'cha bor. Har bir ko'cha ikkita chorrahani tutashtiradi va uni bosib o'tish 1 daqiqa vaqt oladi.
1-chorrahadan n-chorrahaga eng kamida necha daqiqada yetib borish mumkin? Yetib borishning iloji bo'lmasa, −1 chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda n va m. Keyingi m ta qatorning har birida ikkita son u va v — ko'cha tutashtirgan chorrahalar.
Chiquvchi ma'lumotlar
Bitta butun son — eng qisqa yo'l uzunligi yoki −1.
Izoh
2 ≤ n ≤ 10⁵
0 ≤ m ≤ 2·10⁵
1 ≤ u, v ≤ n
Misollar
Kirish #1
4 4 1 2 2 3 3 4 1 3
Chiqish #1
2
Kirish #2
3 1 1 2
Chiqish #2
-1