Masala #0616
Shahzodga yordam
Shahzod o'z ishini yaxshi ko'radi, lekin u ofisiga borish va qaytib kelish uchun ortiqcha vaqt sarflashni yoqtirmaydi. Ko'p yillar davomida ishlagandan so'ng, u oddiy kunlarda ofisiga boradigan eng qisqa masofani biladi.
Yaqinda shaharda turli yo‘llarni muntazam ta’mirlash ishlari boshlandi. Har kuni yo'l to'sib qo'yiladi va o'sha kuni undan hech kim foydalana olmaydi, lekin boshqa barcha yo'llardan foydalanish mumkin.Har kuni siz uning ofisiga borishi mumkin bo'lgan minimal masofani aniqlashingiz kerak.
0 dan gacha raqamlangan ta shahar va ikki yoʻnalishli yoʻllar mavjud.
Kirishning birinchi qatorida ikkita
qatorlar bo'lib, ularning har biri bo'shliqdan ajratilgan uchta
Keyingi qatorda ikkita son . - Shahzod yashaydigan shahar va - uning idorasi joylashgan shahar.
Keyingi qatorda
satrlardan keyin har birida ikkita va butun sonlari mavjud bo'lib,o'sha kuni va o'rtasidagi yo'l to'sib qo'yilgan.
Shahzod borishi mumkin bo'lgan minimal masofani chiqaring (Har bir test uchun alohida). Agar yo'l bo'lmasa, -1 ni chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
4 5 0 1 2 1 2 3 2 3 5 0 3 13 1 3 10 0 3 2 1 2 0 3 |
12 10 |