DMPG '19 S4 - Confusing Crossword Conundrum

View as PDF

Submit solution


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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 N distinct valid words and M unordered pairs of synonyms from that list. The distance between words x and y is the length of the shortest sequence of words w_1, w_2, \ldots, w_k such that w_1 = x, w_k = y, and w_i and w_{i + 1} are synonyms for all 1 \le i < k. If no such sequence exists, the words are unrelated; otherwise, they are related.

In the puzzle, Bob is given Q 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%]

2 \leq N \leq 300
 1 \leq M \leq 500
1 \leq Q \leq 300

Subtask 2 [25%]

2 \leq N \leq 2\ 000
 1 \leq M \leq 5\ 000
1 \leq Q \leq 2\ 000

Subtask 3 [50%]

2 \leq N \leq 100\ 000
 1 \leq M \leq 200\ 000
1 \leq Q \leq 100\ 000

Input Specification

The first line contains three space-separated integers, N, M, and Q.
The next N lines each contain one string consisting of no more than 10 uppercase English letters, the i-th valid word.
The next M lines each contain two distinct space-separated strings, a pair of synonyms. Each pair appears at most once.
The final Q lines each contain one valid word followed by one uppercase English letter, the i-th clue.

Output Specification

Q lines. The i-th line should contain one valid word—the answer to the i-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

There are no comments at the moment.