~/algor $ cat masalalar/eng-qisqa-yol
Graf-02
Eng qisqa yo'l
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
2000 ms
128 MB
45%
Shaharda $n$ ta chorraha va $m$ ta ikki tomonlama ko'cha bor. Chorrahalar $1$ dan $n$ gacha raqamlangan. 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 mumkinligini toping. Yetib borishning iloji bo'lmasa, $-1$ chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son: $n$ va $m$. Keyingi $m$ ta qatorning har birida ikkita natural son: $u$ va $v$ — ko'cha tutashtirgan chorrahalar.
Chiquvchi ma'lumotlar
Bitta butun son — eng kam daqiqalar soni yoki $-1$.
Izoh
$2 \le n \le 10^{5}$
$0 \le m \le 2 * 10^{5}$
$1 \le u, v \le 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