Недавно вы нашли интересную машину, которая оказалась строковым автоматом. Это устройство задаёт некоторый допустимый набор строк и для конкретной строки сообщает, входит ли эта строка в его алфавит.
После некоторого времени вы разобрались в структуре автомата – в нём есть $$$n$$$ вершин и $$$m$$$ направленных рёбер между ними. На каждом ребре написана буква латинского алфавита, а некоторые вершины являются терминальными. В соответствующем графе могут быть петли и кратные рёбра.
Автомат считает строку из латинских символов $$$подходящей$$$, если следующий процесс можно закончить в терминальной вершине.
Изначально $$$x = 1$$$ – текущее состояние. Далее символы строки рассматриваются по очереди. Если из текущей вершины нет перехода по очередному символу $$$s$$$, то процесс заканчивается, и строка считается неподходящей. Если переходы по символу $$$s$$$ есть, то состояние изменяется на одно из состояний, достижимых из $$$x$$$ по букве $$$s$$$.
Обратите внимание на то, что из одной вершины может быть несколько переходов по букве $$$s$$$, однако чтобы строка считалась подходящей, достаточно, чтобы хотя бы 1 путь заканчивался в терминальной вершине.
Дополнительно пустая строка считается $$$подходящей$$$ вне зависимости от структуры автомата.
Необходимо определить максимальную длину строки, которая является $$$подходящей$$$.
Если длина конечна, то нужно вывести лексикографически минимальную строку максимальной длины.
Для строк одинаковой длины $$$S, T$$$ $$$(S \ne T)$$$ $$$S$$$ называется лексикографически меньше, чем $$$T$$$, если существует $$$i$$$, такое что для $$$j$$$ ($$$1 \le j \lt i$$$) $$$S_{j} = T_j$$$ и $$$S_{i} \lt T_i$$$.
В первой строке содержатся числа $$$n, m$$$ и $$$k$$$ ($$$1 \le n, m, k \le 5 \cdot 10^5$$$) – число вершин, рёбер в автомате и количество терминальных вершин.
Далее в $$$m$$$ строках содержатся по 3 числа $$$u, v, s$$$, означающие, что есть направленное ребро от $$$u$$$ к $$$v$$$ с буквой $$$s$$$ $$$(1 \le u,v \le n)$$$, $$$s$$$ – символ латинского алфавита.
В следующей строке содержится $$$k$$$ чисел $$$u_1, u_2, \ldots, u_k\, (1\le u_i \le n)$$$ – терминальные вершины.
В первой строке выведите «inf», если существует сколь угодно длинные $$$подходящие$$$ строки.
Иначе выведите длину самой длинной $$$подходящей$$$ строки, а в следующей строке выведите лексикографически минимальную строку, которая является $$$подходящей$$$.
4 4 21 2 a2 3 b1 3 b4 4 a3 4
2 ab
3 4 11 2 a1 3 c3 2 c2 2 a3
1 c
| Осенний кубок МИФИ 2025 |
|---|
| Закончено |
