## DMPG '19 S4 - Confusing Crossword Conundrum

View as PDF

Points: 12 (partial)
Time limit: 2.5s
Memory limit: 128M

Author:
Problem type

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.

#### 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