prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem C: </font>Weaker than Planned </H1>3 4<p>5The committee members of the Kitoshima programming contest had decided to use crypto-graphic software for their secret communication. They had asked a company, Kodai Software,6to develop cryptographic software that employed a cipher based on highly sophisticated mathematics.7</p>8 9<p>10According to reports on IT projects, many projects are not delivered on time, on budget, with11required features and functions. This applied to this case. Kodai Software failed to implement12the cipher by the appointed date of delivery, and asked to use a simpler version that employed13a type of substitution cipher for the moment. The committee members got angry and strongly14requested to deliver the full specification product, but they unwillingly decided to use this inferior15product for the moment.16</p>17 18<p>19In what follows, we call the text before encryption, plaintext, and the text after encryption,<i>20ciphertext</i>.21</p>22 23<p>24This simple cipher substitutes letters in the plaintext, and its substitution rule is specified with25a set of pairs. A pair consists of two letters and is unordered, that is, the order of the letters26in the pair does not matter. A pair (A, B) and a pair (B, A) have the same meaning. In one27substitution rule, one letter can appear in at most one single pair. When a letter in a pair28appears in the plaintext, the letter is replaced with the other letter in the pair. Letters not29specified in any pairs are left as they are.30</p>31 32<p>33For example, by substituting the plaintext34</p>35<pre>36ABCDEFGHIJKLMNOPQRSTUVWXYZ37</pre>38 39<p>40with the substitution rule {(A, Z), (B, Y)} results in the following ciphertext.41</p>42<pre>43ZYCDEFGHIJKLMNOPQRSTUVWXBA44</pre>45	46<p>47This may be a big chance for us, because the substitution rule seems weak against cracking.48We may be able to know communications between committee members. The mission here is to49develop a deciphering program that finds the plaintext messages from given ciphertext messages.50</p>51 52<p>53A ciphertext message is composed of one or more ciphertext words. A ciphertext word is54generated from a plaintext word with a substitution rule. You have a list of candidate words 55containing the words that can appear in the plaintext; no other words may appear. Some words56in the list may not actually be used in the plaintext.57</p>58 59<p>60There always exists at least one sequence of candidate words from which the given ciphertext61is obtained by some substitution rule. There may be cases where it is impossible to uniquely62identify the plaintext from a given ciphertext and the list of candidate words.63</p>64 65 66<H2>Input</H2>67 68<p>69The input consists of multiple datasets, each of which contains a ciphertext message and a list70of candidate words in the following format.71</p>72 73<p>74<i>n</i><br>75<i>word</i><sub>1</sub><br>76.<br>77.<br>78.<br>79<i>word</i><sub>n</sub><br>80<i>sequence</i>81</p>82 83<p>84<i>n</i> in the first line is a positive integer, representing the number of candidate words. Each of the85next <i>n</i> lines represents one of the candidate words. The last line, sequence, is a sequence of one86or more ciphertext words separated by a single space and terminated with a period.87</p>88 89<p>90You may assume the number of characters in each <i>sequence</i> is more than 1 and less than or91equal to 80 including spaces and the period. The number of candidate words in the list, <i>n</i>, does92not exceed 20. Only 26 uppercase letters, A to Z, are used in the words and the length of each93word is from 1 to 20, inclusive.94</p>95 96<p>97A line of a single zero indicates the end of the input.98</p>99 100<H2>Output</H2>101<p>102For each dataset, your program should print the deciphered message in a line. Two adjacent103words in an output line should be separated by a single space and the last word should be104followed by a single period. When it is impossible to uniquely identify the plaintext, the output105line should be a single hyphen followed by a single period.106</p>107 108<H2>Sample Input</H2>109<pre>1104111A112AND113CAT114DOG115Z XUW ZVX Z YZT.1162117AZ118AY119ZA.1202121AA122BB123CC.12416125A126B127C128D129E130F131G132H133I134J135K136L137M138N139O140ABCDEFGHIJKLMNO141A B C D E F G H I J K L M N O ABCDEFGHIJKLMNO.1420143</pre>144 145<H2>Output for the Sample Input</H2>146<pre>147A DOG AND A CAT.148AZ.149-.150A B C D E F G H I J K L M N O ABCDEFGHIJKLMNO.151</pre>