Потребление мозгов
Два зомби играют в игру. Цель игры состоит в том, чтобы есть мозги. Конечно же, Вашего оппонента. Игра состоит в перемещении фишки в форме мозга по доске. Доска имеет несколько кругов со стрелками между ними. На каждой стрелке написана маленькая английская буква. Не существует двух исходящих стрелок из одного круга, имеющих одну и ту же букву. Когда игра начинается, игроки выбирают специальное выигрышное слово, затем помещают фишку в стартовый круг и начинают делать ходы. В каждом ходе зомби бросает кубик с буквами 'a'. . . 'z', которые выпадают с одинаковой вероятностью. После этого перемещают фишку по стрелке с выпавшей буквой, исходящей из текущего круга, и ход передается противнику. Если стрелка с выпавшей буквой отсутствует, то игрок снова бросает кубик и так далее. Буквы, по которым происходит перемещение по стрелкам, записываются для формирования строки. Когда выигрышное слово появляется в качестве подстроки этой строки в первый раз, игра останавливается, и зомби, который совершил последний ход, побеждает и съедает мозг своего противника.
Есть одна вещь, о которой Вы должны знать. Древняя легенда гласит, что есть существо, которое спит глубоко в океане. Тот, кто напишет магическую фразу, разбудит это существо. Однажды пробудившись, оно будет есть мозги всех. Настоящая опасность этой фразы состоит в том, что для пробуждения злого существа достаточно написать какой-то другой текст, содержащий магическую фразу, как подпоследовательность букв. Очевидно, что два бедных зомби, играющих в игру, могут в конечном итоге написать что-то, что содержит магическую фразу, таким образом, приближая Апокалипсис к каждому, включая самих себя.
Прочитав все это, Вы, скорее всего, зададитесь вопросом, сколько ходов потребуется, пока не будет съеден чей-то мозг. Более конкретно, Вас интересует статистическое ожидание количества ходов до этого события. Напишите программу, чтобы удовлетворить Ваше любопытство.
Входные данные
Первая строка содержит два целых числа n и m - количество кругов на игровой доске и количество стрелок соответственно (1 ≤ n ≤ 20). Каждая из следующих m строк содержит описание одной стрелки в формате "u v c" (без кавычек). Стрелка идет от u-го до v-го круга и содержит букву c. Круги пронумерованы от 1 до n, каждый круг имеет хотя бы одну исходящую стрелку. Стартовый круг всегда имеет номер 1. Далее следуют две строки. Первая строка содержит слово, выбранное зомби, второе - магическая фраза. И слово и магическая фраза непустые и состоят только из английских букв нижнего регистра. Слово содержит не более 10 букв, фраза - не более 50 букв.
Выходные данные
Вывести одно число с как минимум двумя десятичными знаками - ответ на задачу. Если существует ненулевая вероятность того, что игра никогда не закончится, выведите "Infinity". Гарантируется, что если ответ будет конечным, он не будет превышать 10^6.