Rəngli sehrbazlar
Nağıl ölkəsi, iki istiqamətli yollarla birləşdirilmiş bir çox şəhərdən ibarətdir. Ölkənin istənilən şəhərindən digər istənilən şəhərə ya birbaşa, ya da digər şəhərlər vasitəsilə çatmaq mümkündür. Məlumdur ki, nağıl ölkəsində bir şəhəri özünə birləşdirən yollar yoxdur və istənilən iki fərqli şəhər arasında ən çox bir yol mövcuddur.
Nağıl ölkəsində sarı və mavi sehrbazlar yaşayır. Sarı sehrbaz bir yoldan keçərkən onu sarı rəngə boyayır, mavi sehrbaz isə mavi rəngə. Məlum olduğu kimi, sarı rəng mavinin üzərinə və ya mavi rəng sarının üzərinə tətbiq edildikdə, rənglər qarışır və hər iki sehrbazın ən sevmədiyi yaşıl rəngə çevrilir.
Bu il ölkənin paytaxtında (şəhər f) sehrbazlar konfransı keçirilir. Buna görə də sarı və mavi sehrbazlar paytaxta çatmaq üçün minimum neçə yolu yaşıl rəngə boyamaları lazım olduğunu bilmək istəyirlər. Başlanğıcda bütün yollar boyasızdır.
Sarı və mavi sehrbazların başlanğıc mövqeyi əvvəlcədən məlum deyil. Buna görə də, onların başlanğıc yerləşmələrinin k mümkün halları üçün bu problemi həll etmək lazımdır.
Giriş məlumatları
Birinci sətir nağıl ölkəsindəki şəhərlərin sayı n (1 ≤ n ≤ 100) və yolların sayı m (1 ≤ m ≤ 500) göstərir. Üçüncü sətir nağıl ölkəsinin paytaxtı olan şəhərin nömrəsi f (1 ≤ f ≤ n) göstərir. Növbəti m sətirdə ölkənin yollarının təsviri verilir. Bu m sətirdə hər biri iki tam ədəd a[i] və b[i] yazılmışdır ki, bu da a[i] və b[i] şəhərlərini birləşdirən bir yolun mövcud olduğunu göstərir. Növbəti sətir sehrbazların mümkün başlanğıc yerləşmələrinin sayı k (1 ≤ k ≤ 100) göstərir. Sonra k sətir gəlir, hər biri sarı və mavi sehrbazların əvvəlcə yerləşdiyi şəhərlərin nömrələrini göstərən iki tam ədəd ehtiva edir.
Çıxış məlumatları
Hər bir k hal üçün sehrbazların paytaxta çatmaq üçün yaşıl rəngə boyamaları lazım olan minimum yol sayını çıxış edin.