Путешествующий дурак
Вы, вероятно, слышали о "Задаче коммивояжера". Здесь мы обсуждаем другую задачу, известную как "Задача путешествующего дурака". Представьте, что у нас есть 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 } будут игнорироваться.