Səyahət Edən Axmaq#6949
Siz "Səyahət edən Satıcı Problemi" haqqında eşitmiş ola bilərsiniz. Burada isə "Səyahət edən Axmaq Problemi" adlanan başqa bir problemdən bəhs edirik. Təsəvvür edin ki, n şəhər m tək istiqamətli yollarla birləşir. Hər bir yol böyük ingilis hərfi ilə işarələnib (yəni 'A'dan 'Z'yə qədər). İki şəhər arasında bir neçə yol ola bilər, lakin heç bir yol eyni şəhərdə başlayıb bitməyəcək.
Səyahət edən axmaq s şəhərindən səyahətinə başlayır və ya t şəhərinə çatana qədər, ya da t şəhərinə çatılması mümkün olmayan bir şəhərə çatana qədər səyahətini davam etdirir. Əgər o, u şəhərindədirsə, u şəhərindən başlayan istənilən yolu bərabər ehtimalla seçə bilər.
O, eyni şəhəri/yolu bir neçə dəfə ziyarət edə bilər, lakin t şəhərinə çatdıqda dərhal səyahətini dayandırır və yol boyunca qarşılaşdığı yol etiketlərini ziyarət etdiyi sırada xatırlayır. Əgər səyahət etdiyi yoldakı yol etiketləri palindrom əmələ gətirirsə, özünü şanslı hesab edir. Əgər t şəhərinə çata bilmirsə və ya yol etiketləri etibarlı palindrom əmələ gətirmirsə, özünü bədbəxt hesab edir. Şəhərlər, yollar, s və t verildikdə, Səyahət edən Axmaqın şanslı olma ehtimalını tapa bilərsinizmi?
Giriş bir tam ədəd T (≤ 100) ilə başlayır, test hallarının sayını göstərir. Hər bir hal boş bir sətirlə başlayır. Növbəti sətir iki tam ədəd n (2 ≤ n ≤ 12) və m (0 ≤ m ≤ 1000) ehtiva edir. Növbəti m sətirdən hər biri iki tam ədəd, u v (0 ≤ u, v < n, u ≠ v) və böyük ingilis hərfi w ehtiva edir, bu o deməkdir ki, u şəhərindən v şəhərinə tək istiqamətli yol var və yol etiketi w-dir. Növbəti sətir sorğuların sayını göstərən bir tam ədəd (1 ≤ q ≤ 150) ehtiva edir. Növbəti q sətirdən hər biri s t (0 ≤ s, t < n, s ≠ t) göstərən iki tam ədəd ehtiva edir.
Hər bir hal üçün əvvəlcə hal nömrəsini çap edin. Sonra hər bir sorğu üçün göstərilən ehtimalı çap edin.
10^{-4 }-dən az olan səhvlər nəzərə alınmayacaq.
Nümunə 1