Yol hərəkəti qaydaları#5771
Bakıda, kiçik bir ölkənin paytaxtında, vəziyyət olduqca mürəkkəbdir. Uzun kilometrlərlə davam edən tıxaclar şəhərdə hərəkəti demək olar ki, iflic edib. Hakimiyyət bir çox küçələrdə bir tərəfli hərəkət tətbiq etsə də, şəhərin bir yerindən digərinə qaydaları pozmadan keçmək mümkün olub-olmadığını hələ analiz etməyiblər. Paytaxtın nəqliyyat sistemi N meydan və onları birləşdirən M hərəkət zolağından ibarətdir, o cümlədən meydandan keçən dairəvi zolaqlar. Hər bir zolaq yalnız müəyyən bir istiqamətə hərəkət üçün nəzərdə tutulub. Magistrallarda isə həm bir, həm də digər istiqamətə yönəlmiş zolaqlar var. Dairəvi zolaqda yalnız meydanın içində və yalnız saat əqrəbi istiqamətinin əksinə hərəkət etmək mümkündür.
Şəhər hakimiyyəti hər bir zolaqda videokamera yerləşdirib. Buna görə də, əgər İnnokentiy əks istiqamətdə hərəkət edərsə (əgər varsa) və ya bir tərəfli hərəkət zamanı nişanlarla təyin olunmuş istiqamətə əks istiqamətdə hərəkət edərsə, qaydaları pozaraq hər bir zolaq üzrə hərəkət etdikdən sonra ona bu ölkənin min tuqrik məbləğində cərimə ödəmək lazım gələcək.
İnnokentiy, endirimlə kafel plitəsi almağa tələsdiyi üçün, qaydaları pozmaq bahasına olsa belə, mağazaya çatmağa qərar verib. Lakin o, cərimənin ümumi məbləğinin minimal olduğu bir marşrut seçmək istəyir.
İnnokentiy hələ haradan və hansı mağazaya gedəcəyini qərarlaşdırmayıb, buna görə də ona bir neçə sualın cavabını tapmaq lazımdır: A nöqtəsindən B nöqtəsinə çatmaq üçün hansı minimal cəriməni ödəmək lazımdır? Paytaxt sakinlərinin ehtiyaclarına cavab olaraq, məşhur axtarış sistemi İndeks müvafiq xidmət hazırlayır.
Çünki bir çoxunuz gec-tez bu şirkətdə işə qəbul müsahibəsindən keçəcəksiniz, bu məsələnin həllini bacardığınızı göstərin.
Giriş məlumatlarının ilk sətirində şəhərdəki meydanların və hərəkət zolaqlarının sayı olan iki ədəd N və M verilir (1 ≤ N ≤ 5000, 1 ≤ M ≤ 10000). Daha sonra hərəkətə icazə verilən zolaqların təsvirləri verilir. Hər bir zolaq, birinci göstərilən meydandan ikinciyə doğru hərəkətə icazə verildiyi meydanların nömrələri ilə təsvir olunur.
Növbəti sətirdə İnnokentinin suallarının sayı olan bir ədəd K verilir (1 ≤ K ≤ 10000, N·K ≤ 2·10^7). Növbəti sətirlərdə suallar təsvir olunur, hər bir sual, birinci göstərilən meydandan ikinciyə qədər ən ucuz yolu tapmaq lazım olan meydanların nömrələri ilə təsvir olunur.
Hər bir sual üçün bir ədəd çıxarın — axtarılan minimal cərimə məbləği min tuqriklərlə. Əgər seçilmiş meydan cütü arasında yol yoxdursa, -1 çıxarın.
Nümunə 1