Word Ladder

Time limit1sMemory limit256 MB

Summary

Find the shortest chain between each queried word pair where neighbors differ by one letter, printing the lexicographically first among the shortest.

Level: Medium5 of 10
Topics: BFS, Graph, Greedy
Solved: No attempts yet

Problem

The minions keep studying English, and they play games to grow their vocabulary. One of the games is the word ladder. A word ladder, also called Doublets, word links, or word golf, is a word game invented by Lewis Carroll.

A puzzle starts with two words. You solve it by finding a chain of words that links the two, where any two neighbouring words in the chain differ in exactly one letter.

For example, given COLD and WARM, this is a word ladder.

COLD --> CORD --> CARD --> WARD --> WARM

This is another one.

COLD --> WOLD --> WORD --> WARD --> WARM

The player who finds the shortest ladder between the two given words wins. If two players find ladders with the same number of words, compare the ladders word by word from the front. At the first position where the ladders differ, the player whose word comes earlier in lexicographic order wins. Comparing the two ladders above, CORD comes before WOLD, so the first ladder wins.

Kevin the minion plays with one fixed dictionary. Every word of a ladder, including the two end words, must be in that dictionary. Two words are neighbours only when they have the same length and differ in exactly one position, so words of different lengths are never neighbours. Find the winning ladder for each pair of words.

Input

The first line contains the number of test cases $T$ .

Each test case gives one dictionary and a list of word pairs. It begins with the number of words in the dictionary $N$ , followed by the $N$ words. Then comes the number of pairs $Q$ for which you have to find a ladder, followed by the $Q$ pairs. One pair is two words.

All numbers and words are separated by whitespace, and the line breaks are arbitrary. Every word consists of lowercase English letters (gru, not Gru).

$1 \le T \le 9$
$1 \le N \le 1000$
$1 \le Q \le 20$
Each word has length between $1$ and $10$ .
The words of one dictionary are pairwise distinct.
Both words of every pair belong to that dictionary.

Output

For each pair, in the order given in the input, print one line.

If a ladder exists, print it in this format.

Word ladder from A to B: w1 --> w2 --> ... --> wk

Here $A$ is the first word of the pair, $B$ is the second word, and $w_1, \dots, w_k$ are the words of the ladder. Print a ladder with the fewest words; if several shortest ladders exist, print the one whose word sequence comes first in lexicographic order. Join the words of the ladder with --> (a space, two hyphens, a >, and a space).

If no ladder exists, print this line.

No word ladder from A to B using the input dictionary.

When $A$ and $B$ are the same word, the ladder is that single word, so the line reads Word ladder from A to A: A.

Examples3

Example 1

Input

2
6 abc abd acd bcd bdd xyz 2 abc bdd abc xyz
10 man can con bow cow mow han ban bon how 1 man how

Expected output

Word ladder from abc to bdd: abc --> abd --> acd --> bcd --> bdd
No word ladder from abc to xyz using the input dictionary.
Word ladder from man to how: man --> ban --> bon --> bow --> how

Example 2
Input
```
1
1 a 1 a a
```
Expected output
```
Word ladder from a to a: a
```

Example 3

Input

1
5 cat cot cog dog bird 3 cat dog cat bird bird bird

Expected output

Word ladder from cat to dog: cat --> cot --> cog --> dog
No word ladder from cat to bird using the input dictionary.
Word ladder from bird to bird: bird