09. Игра в замены

Маленькая Варечка (из тех удивительных детей, которые что-то странное делают в задачах питерской олимпиады по программированию для 3-7 классов) освоила замены символов в текстовом редакторе и занялась лингвистическими экспериментами. Девочка, не глядя в текст, придумывала, какие буквы на какие она заменит. Потом выделяла несколько слов, выполняла намеченные замены в выделенном тексте, читала вслух то, что получилось, смеялась, а потом производила в обратном порядке обратные замены, чтобы вернуть тексту прежний вид. Однако почему-то не всегда слова приобретали первоначальный вид. Варечка стала внимательней планировать замены: каждую букву алфавита она использовала не более одного раза, либо как заменяемую, либо как замещающую. Но это не помогло.

Разработайте программу, которая получает на вход описание последовательности замен и слова, и для каждого слова проверяет, восстановится ли оно в прежнем виде, если после прямых замен выполнить в обратном порядке обратные.

Входные данные. В первой строке через пробел — натуральные числа T и W - количество трансформаций и количество анализируемых слов. Т не больше 13, W не превышает 100. В следующих T строках вводятся пары букв, описывающих замены (две строчных буквы латиницы без пробела, при прямых заменах первая заменяется на вторую, при обратных - вторая на первую). Далее следуют W строк со словами для анализа. Строки состоят из строчных букв латиницы, длина каждой строки не превышает 1000 символов.