Cütlüklərin Qoşulması
Hava trafik qaydalarına görə, Nlogoniya şəhərlərində hər bir şəhərdən yalnız bir başqa şəhərə uçuş qeydiyyata alınmalıdır. Sərnişinlər bu uçuşlardan yalnız qeyd olunan istiqamətdə istifadə edə bilərlər, yəni şəhər X-dən şəhər Y-yə uçuş varsa, əks istiqamətdə uçuş olmayacaq. Beləliklə, qeydiyyatdan keçmiş uçuşların sayı şəhərlərin sayına bərabərdir. Bu qayda hava səyahətini bir qədər çətinləşdirir, lakin ənənə və Kraliçanın güclü hökmü hər hansı bir dəyişikliyi çətinləşdirir. Hətta bəzi şirkətlər bu qaydanın yaratdığı problemlərdən qazanc əldə edirlər.
Cütlərin Uyğunlaşdırılması Assosiasiyası (ACM) müştərilərə uzun müddətli ruh yoldaşlarını tapmağa kömək etmək üçün yeni bir xidmət təqdim edir: İnternet Cütlər üçün Bağlantı Proqramı (ICPC). Bu xidmət, bir cütlüyün bir-biri ilə görüşməsi üçün lazım olan minimum ümumi uçuş sayını hesablamağa kömək edir (bəlkə də onların heç birinin yaşamadığı bir şəhərdə). Cütlüyün başlanğıc şəhərləri A və B olduğunu qəbul edərək, agentlik C şəhərini tapmağa çalışacaq ki, C həm A, həm də B şəhərlərindən hava yolu ilə əlçatan olsun və A-dan C-yə getmək üçün lazım olan uçuşların sayı ilə B-dən C-yə getmək üçün lazım olan uçuşların sayı cəmi minimum olsun. Qeyd edək ki, C A və ya B və ya hər ikisinə bərabər ola bilər.
Sizə mövcud olan bütün uçuşların siyahısı və bir cütlüyün yaşadığı şəhərlərin cütlərindən ibarət sorğuların siyahısı veriləcək. Hər bir sorğu üçün onların görüşməsi üçün lazım olan minimum ümumi uçuş sayını hesablamalısınız.
Giriş verilənləri
Hər bir test halı bir neçə sətirdə təsvir edilir. Birinci sətir şəhərlərin sayını göstərən N tam ədədini ehtiva edir (2 ≤ N ≤ 10^5). Şəhərlər 1-dən N-ə qədər müxtəlif tam ədədlərlə müəyyən edilir. İkinci sətir N tam ədədi F_i ehtiva edir, burada F_{i } şəhər i-dən qeydiyyatdan keçmiş uçuşun şəhər F_i-yə olduğunu göstərir (1 ≤ F_i ≤ N, F_i ≠ i üçün i = 1, 2, ..., N). Üçüncü sətir sorğuların sayını göstərən Q tam ədədini ehtiva edir (1 ≤ Q ≤ 10^5). Növbəti Q sətirin hər biri cütlüyün başlanğıc şəhərlərini göstərən iki tam ədəd A və B təsvir edir (1 ≤ A, B ≤ N). Hər bir test halında, əgər şəhər X-dən şəhər Y-yə hava yolu ilə səyahət etmək mümkündürsə, bunu etmək üçün lazım olan maksimum uçuş sayı 10^4-dir.
Çıxış verilənləri
Hər bir test halı üçün Q sətir çıxış edin. i-ci sətirdə i-ci sorğuya cavab olaraq bir tam ədəd yazın. Əgər müvafiq cütlük hava yolu ilə görüşə bilirsə, onların bir-biri ilə görüşməsi üçün lazım olan minimum ümumi uçuş sayını yazın; əgər cütlüyün hava yolu ilə görüşməsi mümkün deyilsə, '-1' ədədini yazın.