Nağıllar ölkəsi özündə ikitərəfli yollarla birləşdirilmiş çoxlu şəhərləri təmsil edir. Bununla belə, ölkənin ixtiyari bir şəhərində istənilən digərinə birbaşa və yaxud digər şəhərdən keçməklə çatmaq olar. Məlumdur ki, nağıllar ölkəsində şəhərin özünü özü ilə birləşdirən yol yoxdur və ixtiyari iki müxtəlif şəhər arasında birdən artıq yol yoxdur.

Nağıllar ölkəsində sarı və göy sehrbazlar yaşayır. Sarı sehrbazlar yol ilə gedərkən onu sarı, göylər isə göy rənglə boyayırlar. Məlum olduğu kimi, göy rəngin üzərinə sarı rəng, yaxud sarı rəngin üzərinə göy rəng çəkdikdə boyalar qarışır və hər iki sehrbazın ən çox xoşlamadığı yaşıl rəngə çevrilir.

Bu il ölkənin paytaxtında (F şəhərində) sehrbazların konfransı keçirilir. Ona görə də sarı və göy sehrbazlar bilmək istəyirlər ki, onlara paytaxta gedib çatmaq üçün hansı ən az sayda yaşıl rəngli yolu rəngləmək lazım gələcək. Başlanğıcda bütün yollar rənglənməmişdir. Sarı və göy sehrbazların ilkin vəziyyəti əvvəlcədən məlum deyil. Ona görə də onların bütün mümkün ilkin k yerləşdirmə hallarının hamısı üçün verilmiş məsələni həll etmək zəruridir.

Giriş verilənləri

Giriş faylının birinci sətrində uyğun olaraq nağıllar ölkəsindəki şəhərlərin və yolların sayı olan n (1 ≤ n ≤ 105) və m (1 ≤ m ≤ 500000) tam ədədləri yerləşir. İkinci sətirdə nağıllar ölkəsinin paytaxt olan şəhərin nömrəsi olan tam F (1 ≤ F ≤ n) ədədi yerləşir. Sonrakı m sayda sətirdə ölkənin yollarının təsviri verilir. Bu m sətirdə ai və bi şəhərlərini birləşdirən yolların olduğunu bildirən iki tam ai və bi ədədləri yazılır. Sonrakı sətirdə sehrbazların bütün mümkün ilkin yerləşmə vəziyyətlərinin sayı olan k (1 ≤ k ≤ 105) tam ədədi yerləşir. Sonra isə hər birində iki tam ədəd - başlanğıcda sarı və göy sehrbazların olduğu şəhərlərin nömrəsi yerləşən k sayda sətir gəlir.

Çıxış verilənləri

Hər bir k halı üçün sizin proqram paytaxta gedib çatmaq üçün sehrbazların yaşıl rənglə boyamalı olduğu ən az sayda yolların sayını verməlidir.