Мандрівний Дурень
Ви, напевно, чули про "Задачу комівояжера". Тут ми розглядаємо іншу задачу під назвою "Задача мандрівного дурня". Припустимо, що є n міст, з'єднаних m односторонніми дорогами. Кожна дорога позначена великою англійською літерою (тобто від 'A' до 'Z'). Між двома містами може бути кілька доріг, але жодна дорога не починається і не закінчується в одному й тому ж місті.
Мандрівний дурень починає свою подорож з міста s і продовжує її, поки не досягне t, або поки не досягне міста, з якого t недосяжне. Якщо він знаходиться в місті u, він може вибрати будь-яку дорогу, що починається з u, з однаковою ймовірністю.
Він може відвідати те саме місто/дорогу більше одного разу, але як тільки він досягає t, він негайно зупиняє свою подорож і запам'ятовує мітки доріг, які він знайшов на своєму шляху, в тому ж порядку, в якому дороги були пройдені. Якщо мітки доріг на його шляху утворюють паліндром, він вважає себе щасливим. Якщо він не може досягти t або мітки доріг не утворюють дійсний паліндром, він вважає себе нещасливим. Враховуючи міста, дороги, s і t, чи можете ви визначити ймовірність того, що мандрівний дурень буде щасливим?
Вхідні дані
Вхід починається з цілого числа T (≤ 100), що позначає кількість тестових випадків. Кожен випадок починається з порожнього рядка. Наступний рядок містить два цілі числа n (2 ≤ n ≤ 12) і m (0 ≤ m ≤ 1000). Кожен з наступних m рядків містить два цілі числа, u v (0 ≤ u, v < n, u ≠ v) і велику англійську літеру w, що означає, що є одностороння дорога з міста u до міста v, і мітка дороги - w. Наступний рядок містить ціле число (1 ≤ q ≤ 150), що позначає кількість запитів. Кожен з наступних q рядків містить два цілі числа, що позначають s t (0 ≤ s, t < n, s ≠ t).
Вихідні дані
Для кожного випадку спочатку надрукуйте номер випадку. Потім для кожного запиту надрукуйте ймовірність, як зазначено.
Помилки менше 10^{-4 } будуть ігноровані.