One To One
During the Second Foobarian War of the 19th century, intelligence
agents for the nation of Foovania relied heavily on the use of
translation codebooks for communicating with their agents. In such a
codebook, all of the words that were deemed likely for an agent to
need to transmit were given replacement words. For example, a
codebook might indicate that "army" be replaced with "apple", and
"general" be replaced with "cornfield." So long as replacements were
chosen wisely, and the codebooks were kept away from Barvarian agents,
this was considered a very good method of communicating.
However, as the war dragged on the tendency to concatenate codebooks
became more and more common. In these situations, there might be more
than one codeword for a plain-text word, or more than one plain-text
decoding of a codeword. For example, if one codebook replaced "army"
with "apple" and another replaced "army" with "duck", this gives the
agent in the field options for encoding (not a bad thing). But if one
codebook replaced "army" with "apple" and a second replaced
"artillery" with "apple", then the decoders couldn't necessarily know
which was the intended meaning (a very bad thing.)
Your task is to read in a collection of codebook entries and an
encoded message, and decide if there is exactly one way of decoding
it.
Input Spec
You will first be given an integer N (1 <= N <= 10000)
indicating the number of codebook entries available to the agent in
question. Then you will read in N codebook entries (pairs of
single-word strings). The remainder of the input will be the agent's
message. (Read until EOF.)
Output Spec
If the given coding and message has a unique decoding, print "Valid
message." followed by the decoding. If not, print "Invalid message."
In either case, print a newline character.
Test Files
Sample input 1
Sample output 1
Sample input 2
Sample output 2
Sample input 3
Sample output 3