Задача №111769. Шифр
Жюри N-ской олимпиады по информатике решило зашифровать свои материалы подстановочным шифром. Для шифрования таким шифром задаётся взаимно-однозначное соответствие между буквами алфавита в открытом (т. е. до шифрования) тексте и буквами алфавита в закрытом (т. е. после шифрования) тексте, это соответствие и является ключом шифра. В процессе шифрования каждая буква в открытом тексте заменяется на соответствующую ей букву в закрытом тексте, порядок букв в слове при этом не меняется.
Однако, память у членов жюри оказалась уже не та, что в молодые годы, поэтому часто они путали, какие буквы надо было заменять на какие. В результате теперь они не могут восстановить свои материалы, а олимпиада уже на носу!
Чтобы разрешить свои проблемы, они обратились к вам. Для облегчения вашей задачи они выписали на бумажку все возможные варианты зашифрования букв, которые они могли применять, в виде набора пар "открытая буква" и "зашифрованная буква". Также вам известны все пары букв N-ского алфавита, которые могут следовать одна за другой в открытом тексте. Ваша задача состоит в том, чтобы по заданному зашифрованному слову сказать, соответствует ли ему хоть одно расшифрованное слово, единственен ли вариант расшифровки, и привести пример вариантов расшифровки слова. Слово A считается возможной расшифровкой слова B, если, во-первых, его можно "зашифровать" (заменяя каждую букву на одну из соответствующих ей "зашифрованных" букв), получив слово B, и, во-вторых, каждая пара букв слова A, стоящих рядом, является допустимой для N-ского языка.
N-ский язык пользуется латинским алфавитом из 26 букв, регистр букв N-ское жюри не интересует, поэтому везде в открытом тексте используются большие буквы, а в закрытом — маленькие.
На первой строке входного файла находится одно целое число M (0 ≤ M ≤ 676) — число пар открытых — "зашифрованных" букв, указанных на бумажке, переданной N-ским жюри. Далее следуют M строк, на каждой находятся два символа — сначала открытая буква, потом вариант её "зашифрования". Пары не повторяются.
На следующей строке находится одно целое число K (0 ≤ K ≤ 676) — число пар открытых букв, которые могут идти одна за другой. Далее следуют K строк, на каждой из которых по две открытые буквы, образующие такую пару. Пары не повторяются. Заметим, что возможна ситуация, когда последовательность букв "AB" в слове допустима, а "BA" — нет, в этом случае списке будет дана только пара "AB", а пары "BA" не будет.
На следующей строке расположено одно целое число N (1 ≤ N ≤ 500) — длина зашифрованного слова, а на следующей строке — само слово (N маленьких латинских букв).
Может оказаться так, что какой-то открытой букве не соответствует ни одна "зашифрованная"; это означает, что эта буква в открытом тексте не использовалась.
Если вариантов дешифрования нет ни одного, в первую строку выходного файла выведите "no"
Если вариант дешифрования ровно один, в первую строку выходного файла выведите "only" , а во вторую — дешифрованное слово.
Если вариантов дешифрования больше одного, в первую строку выходного файла выведите "many" , а во вторую и третью и любые два различных варианта дешифрования слова.
0 0 1 u
no
4 Ju Cu Uo Ko 3 JC UJ JK 3 ouo
only UJK