AL10-2. Eng qisqa yo‘l

Graf va ikki uch s, t berilgan. s dan t ga borish uchun eng kamida nechta qirradan o‘tish kerak? Yo‘l bo‘lmasa -1.

BFS uchlarni masofasi bo‘yicha qatlam-qatlam ochadi: avval 1 qadamdagilar, keyin 2 qadamdagilar va hokazo. Navbat uchun collections.deque.

Kirish ma’lumotlari

Birinchi qatorda uchlar soni n va qirralar soni m. Keyingi m qatorda qirra: ikki uch raqami a b. Uchlar 1 dan n gacha; takroriy qirra va sirtmoq yo‘q. Oxirgi qatorda s t.

Chiqish ma’lumotlari

Qirralar soni yoki -1.

Cheklovlar

1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2·10⁵