Time Limit: Java: 10000 ms / Others: 10000 ms
Memory Limit: Java: 32768 KB / Others: 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 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#.
14 BE CHANGE FIRST IN IS MUST SAMPLE SEE THE THIS TO WISH WORLD YOU 4 GSRH RH GSV URIHG HZNKOV IZM BMVU SP UGP RGTANP IZM KFVG UZ VPP FA UGP KZWCQ XYZ ABCDEFG XZY ABD
Z***VU*SR**ON**K*IHG****** TSRQP*NGF**CBAZ**WVUM*K*I* #No solution# #More than one solution#