Bob is trying to solve a crossword puzzle, but he doesn't have the patience to do it. So naturally, he wants you to write a program to help him.
Bob has compiled a list of distinct valid words and unordered pairs of synonyms from that list. The distance between words and is the length of the shortest sequence of words such that , , and and are synonyms for all . If no such sequence exists, the words are unrelated; otherwise, they are related.
In the puzzle, Bob is given clues of the form
a b, where
a is a valid word and
b is an uppercase English letter. The answer to each clue is the word that has the shortest distance from
a, of all the valid words starting with
b that are related to
a. If none of the words starting with
b are related to
a, there is no answer. If multiple answers are possible, the correct one is the lexicographically lowest of them.
Please help Bob solve the puzzle!
Subtask 1 [25%]
Subtask 2 [25%]
Subtask 3 [50%]
The first line contains three space-separated integers, , , and .
The next lines each contain one string consisting of no more than uppercase English letters, the -th valid word.
The next lines each contain two distinct space-separated strings, a pair of synonyms. Each pair appears at most once.
The final lines each contain one valid word followed by one uppercase English letter, the -th clue.
lines. The -th line should contain one valid word—the answer to the -th clue—or
-1 if there is no answer. If there are multiple valid answers, output the lexicographically lowest one.
6 4 4 AA AB AC CCC BBB EA AA CCC AB BBB AC CCC CCC BBB BBB A BBB B CCC A BBB E
AB BBB AA -1