Rəngli sehrbazlar - 2#1933
Nağıl ölkəsi bir-biri ilə iki istiqamətli yollarla bağlı bir neçə şəhərdən ibarətdir. Ölkənin istənilən şəhərindən başqa bir şəhərə, ya birbaşa, ya da digər şəhərlər vasitəsilə çatmaq mümkündür. Heç bir şəhər öz-özü ilə birbaşa bağlı deyil və istənilən iki müxtəlif şəhər arasında ən çox bir yol mövcuddur.
Bu ölkədə sarı və mavi sehrbazlar yaşayır. Sarı sehrbaz bir yol ilə gedəndə onu sarıya boyayır. Mavi sehrbaz isə bir yol ilə gedəndə onu mavi rəngə boyayır. Əgər mavi ilə boyanmış yol sarıya (və ya sarı ilə boyanmış yol mavi rəngə) boyanarsa, rənglər qarışır və yol yaşıl olur — hər iki sehrbazın ən sevmədiyi rəngdir.
Bu il sehrbazların konfransı paytaxtda (şəhər ) keçirilir. Həm sarı, həm də mavi sehrbaz paytaxta çatmaq istəyir və hər ikisinin paytaxta çatması üçün ən az neçə yolun yaşıl olmalı olduğunu bilmək istəyirlər. Başlanğıcda bütün yollar boyanmamış vəziyyətdədir.
Sarı və mavi sehrbazların ilkin yerləri əvvəlcədən bəlli deyil, ona görə də siz bu sualı mümkün başlanğıc ssenarisi üçün cavablandırmalısınız.
Birinci sətirdə iki tam ədəd (1 \le n \le 10^5) və (1 \le m \le 500\,000) — şəhərlərin və yolların sayı verilir.
İkinci sətirdə bir tam ədəd (1 \le F \le n) — paytaxt şəhərinin nömrəsi verilir.
Növbəti sətrin hər birində iki tam ədəd a_i və b_i (1 \le a_i, b_i \le n) verilir — şəhərlər a_i və b_i arasında yol var.
Sonra bir sətirdə bir tam ədəd (1 \le k \le 10^5) — sehrbazların mümkün başlanğıc yerləşmələrinin sayı verilir.
Növbəti sətrin hər birində iki tam ədəd verilir — sarı və mavi sehrbazların ilkin olduğu şəhərlər.
Hər ssenarinin hər biri üçün, hər iki sehrbazın paytaxta çata bilməsi üçün yaşıl olmalı ən az yolun sayını çap edin.
Nümunə 1