Rəngli sehrbazlar#1944
Sehristanda şəhərlər ikitərəfli yollarla birləşdirilib. İstənilən şəhərdən başqa istənilən şəhərə ya birbaşa, ya da digər şəhərlər vasitəsilə getmək mümkündür. Qeyd edək ki, heç bir yol özünü bir şəhərə birləşdirmir və istənilən iki fərqli şəhər arasında ən çoxu bir yol mövcuddur.
Bu diyarda iki sehrbaz var: biri sarı, digəri isə mavi. Sarı sehrbaz yolla gedərkən yolu sarıya boyayır, mavi sehrbaz isə mavi rəngə boyayır. Əgər sarı boyanın üzərinə mavi, yaxud əksinə sürtülərsə, yol yaşıl olur və bu, hər iki sehrbazın xoşuna gəlmir.
Bu il sehrbazlar konfransı paytaxt şəhərində ( şəhəri) keçirilir. Sehrbazlar paytaxta çatmaq üçün ən az neçə yolu yaşıl rəngə boyamalı olduqlarını müəyyənləşdirmək istəyirlər. Əsasən, bütün yollar əvvəlcə boyasızdır.
Sarı və mavi sehrbazların başlanğıc mövqeləri əvvəlcədən müəyyən deyil. Buna görə, məsələnin ehtimal olunan başlanğıc mövqeləri üçün həll olunması tələb olunur.
Birinci sətirdə iki tam ədəd verilir: şəhərlərin sayı (1 \le n \le 100) və yolların sayı (1 \le m \le 500).
İkinci sətirdə paytaxt şəhərinin nömrəsi (1 \le f \le n) verilir.
Növbəti sətrin hər birində yollar təsvir olunur, hər sətirdə iki tam ədəd a_i və b_i verilir; bu, a_i və b_i şəhərləri arasında bir yolun olduğunu göstərir.
Sonrakı sətirdə (1 \le k \le 100) tam ədədi verilir; bu, sehrbazların mümkün başlanğıc yerləşmələrinin sayıdır.
Sonrakı sətrin hər birində iki tam ədəd verilir, müvafiq olaraq sarı və mavi sehrbazların başlanğıc şəhərlərini göstərir.
Hər ssenarinin hər biri üçün, sehrbazların paytaxta çatması üçün ən az neçə yolun yaşıl olması lazım olduğunu çap edin.
Nümunə 1