Word Ladder

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.

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.

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.