Masala #0916

Metro \(N\) ta bekatdan va \(M\) ta bekatlarni o‘zaro bog‘lovchi yo‘llardan tashkil topgan. Agar \(u\) va \(v\) bekatlar orasida yo‘l mavjud bo‘lsa, unda \(u\) dan \(v\) ga yoki \(v\) dan \(u\) ga 1 daqiqada yetib borsa bo‘ladi.

Toshkent shahriga ko’chib kelgan Davlatbek metrodan ko‘p foydalana boshladi. Xususan bugun, Davlatbek \(Q\) marta metrodan foydalanmoqchi. \(i\)-foydalanishida \(a_i\) bekatdan \(b_i\) bekatga borishi haqida aniq reja qildi. Agar metroni kutish va metro almashtirish vaqti inobatga olinmasa, Davlatbek har bir metrodan foydalanishida minimal necha daqiqa vaqtini metroda o‘tkazadi? Agar \(i\)-foydalanishi imkonsiz bo‘lsa −1 chiqaring.

Birinchi qatorda ikkita butun son - \(N\) va \(M\) \((2≤N≤300,1≤M≤ \dfrac{N(N−1)}{2})\) bekatlar soni va bekatlar orasidagi yo‘llari soni kiritiladi.

Keyingi \(M\) ta qatorda ikkitadan butun son - \(u_i\) va \(v_i(1 ≤ v_i, u_i ≤ N )\) kiritiladi. Bu \(u_i\) va \(v_i\) bekatlar orasida yo‘l mavjud ekanligini anglatadi.

So‘ng yangi qatorda yagona butun son - \(Q(1 ≤ Q ≤ 300)\) Davlatbekning bugun metrodan foydalanishlari soni kiritiladi.

Keyingi \(Q\) ta qatorda ikkitadan butun son - \(a_i\) va \(b_i(1 ≤ a_i, b_i ≤ N )\), \(i\)-foydalanishdagi kirish va chiqish bekatlari kiritiladi.

\(i\)-foydalanish uchun \(i\)-qatorda \(a_i\) bekatdan \(b_i\) bekatga yetib borish uchun ketadigan minimal vaqtni chiqaring. Buning imkoni bo‘lmasa \(−1\) chiqaring.