Grafda eng qisqa yoʻl

Shart

Birinchi qatorda uchlar soni n va qirralar soni m berilgan. Keyingi m ta qatorning har birida qirra bogʻlaydigan u va v uchlari berilgan (graf yoʻnalishsiz). 1-uchdan n-uchgacha eng qisqa yoʻldagi qirralar sonini chiqaring. Yoʻl boʻlmasa, -1 chiqaring. n = 1 uchun javob 0.

Misollar

4 4
1 2
2 4
1 3
3 4

2

3 1
2 3

-1

Cheklovlar

• 1 ≤ n ≤ 10^5
• 0 ≤ m ≤ 2·10^5
• 1 ≤ u, v ≤ n