В секретном 240 отделе ИПФ РАН \(N\) сотрудников и \(N\) компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно \(K\) компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно \(K\) сотрудников.

Информация о том, какой сотрудник к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу отдела, сотрудники должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков сотрудников найдёт рассадку сотрудников по компьютерам, удовлетворяющую этим допускам.

Обратите внимание, что значение \(K\) тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что \(K\) будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений \(K\).

Жюри N-ской олимпиады по информатике решило зашифровать свои материалы подстановочным шифром. Для шифрования таким шифром задаётся взаимно-однозначное соответствие между буквами алфавита в открытом (т.е. до шифрования) тексте и буквами алфавита в закрытом (т.е. после шифрования) тексте, это соответствие и является ключом шифра. В процессе шифрования каждая буква в открытом тексте заменяется на соответствующую ей букву в закрытом тексте, порядок букв в слове при этом не меняется.

Однако, память у членов жюри оказалась уже не та, что в молодые годы, поэтому часто они путали, какие буквы надо было заменять на какие. В результате теперь они не могут восстановить свои материалы, а олимпиада уже на носу!

Чтобы разрешить свои проблемы, они обратились к вам. Для облегчения вашей задачи они выписали на бумажку все возможные варианты зашифрования букв, которые они могли применять, в виде набора пар «открытая буква» — «зашифрованная буква». Также вам известны все пары букв N-ского алфавита, которые могут следовать одна за другой в открытом тексте. Ваша задача состоит в том, чтобы по заданному зашифрованному слову сказать, соответствует ли ему хоть одно расшифрованное слово, единственен ли вариант расшифровки, и привести пример вариантов расшифровки слова. Слово \(\mathcal{A}\) считается возможной расшифровкой слова \(\mathcal{B}\), если, во-первых, его можно «зашифровать» (заменяя каждую букву на одну из соответствующих ей «зашифрованных» букв), получив слово \(\mathcal{B}\), и, во-вторых, каждая пара букв слова \(\mathcal{A}\), стоящих рядом, является допустимой для N-ского языка.

... но нужен ли на самом деле кому-нибудь 6\(1\over7\)-пунктовый шрифт, который на три четверти — шрифт Baskerville, и на четверть — Helvetica?

Дональд Э. Кнут. Идея Мета-фонта¹

Маленькая девочка Оля добралась до полки, на которой стоят флаконы с мамиными любимыми духами, и начала заниматься своим любимым занятием — переливанием жидкостей из одного флакона в другой. Когда наконец мама застала её за этим занятием, прекрасная коллекция духов была уже безнадёжно утрачена.

К счастью, Оля — аккуратная девочка, поэтому все свои действия она записывала на бумажку. Помогите ей успокоить маму: определите, каков состав духов в первом (мамином любимом) флаконе, чтобы мама смогла придумать этой смеси новое название и рассказывать всем, какие прекрасные духи она смогла сделать вместе с дочерью.

Считайте, что Оля не пролила ни одной капли, а также что она тщательно встряхивала флаконы после каждого переливания. Учтите, что в маминых флаконах порой не видно, есть ли там жидкость, и потому Оля иногда могла пытаться переливать духи из пустого флакона (в результате, естественно, ничего не переливалось). Вы можете также считать, что после каждого переливания в каждом флаконе каждый тип духов либо полностью отсутствует, либо содержится в объеме не меньшем чем \(10^{-10}\).