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!
Constraints
Subtask 1 [25%]
Subtask 2 [25%]
Subtask 3 [50%]
Input Specification
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.
Output Specification
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.
Sample Input
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
Sample Output
AB
BBB
AA
-1
Comments