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