Time Limit: 10 Seconds
Memory Limit: 32768 KB
The scientific committee members of the 26th ACM/ICPC, who design the contest
problems, use the following encryption algorithm to communicate the problem
drafts securely through the Internet. To encrypt a text, all occurrences of
each letter is replaced with another letter (possibly itself), such that no
two letters are encrypted to the same letter. Both original and encrypted texts
consist of only upper-case letters and blanks. Blanks are not encrypted and
are repeated exactly in the encrypted text. As an example, the string GSRH RH
GSV URIHG HZNKOV is the encrypted form of THIS IS THE FIRST SAMPLE according
to the encryption table (A → Z, B → Y, C → X, …, Z → A).
A recipient of a problem draft has lost the encryption table, but he has a dictionary
which includes all the possible words appearing in the problems. You are to
help him set up a decryption table to enable him restore the original problem
draft from the encrypted one. Given a dictionary of the original words used
in the text, and the encrypted text, we want to find the right encryption table
such that after decrypting the given encrypted text back to the original one,
all words can be found in the dictionary.
The first part of the input is a dictionary of English words common to all test
cases. The first line of the file is d (1 <= d <= 50000); the number of words
in the dictionary, followed by d lines each containing a word in the dictionary.
The words in the dictionary are sorted in alphabetical order and all are in
uppercase. Each word has at most 20 characters, but you can assume that sum
of the length of all words in the dictionary is no more than 350,000. The next
line contains a single integer t (1 <= t <= 10), the number of test cases, followed
by the input data for each test case. Each test case, which is preceded by a
single blank line, consists of multiple lines in the input file forming the
encrypted text. Each line has a string containing only uppercase letters and
blank. You may assume that no line break is occurred in the middle of a word
and there may be arbitrary number of blank characters at the end of each line.
Maximum length of input lines is 80.
The output contains exactly t lines, each corresponding to a test case. Each
line should contain a single string of 26 characters which is the encryption
of the string ABCDEFGHIJKLMNOPQRSTUVWXYZ according to the encryption table used
in the test case. Letters in the output string should be in uppercase. It is
possible that some letters do not appear in the encrypted text at all. In this
case, put a * mark in place of those letters not appearing in the decrypted
version of the input text. If the test case has no solution, the output line
should contain #No solution#. If there is more than one possible encryption
table for a test case, the output line should contain #More than one solution#.
GSRH RH GSV URIHG HZNKOV
IZM BMVU SP UGP
RGTANP IZM KFVG UZ VPP
FA UGP KZWCQ
#More than one solution#
Source: Asia 2001, Tehran (Iran)