단어 사다리

미니언들은 영어를 배우면서 어휘를 늘리려고 여러 놀이를 한다. 그중 하나가 단어 사다리다. 단어 사다리는 Lewis Carroll이 만든 말놀이이고, Doublets, word links, word golf라고도 부른다.

퍼즐은 단어 두 개로 시작한다. 두 단어를 잇는 단어의 사슬을 찾으면 퍼즐이 풀린다. 사슬에서 이웃한 두 단어는 정확히 한 글자만 달라야 한다.

예를 들어 COLD와 WARM이 주어지면 다음이 단어 사다리다.

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

다음도 단어 사다리다.

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

주어진 두 단어를 잇는 가장 짧은 사다리를 찾은 사람이 이긴다. 단어 수가 같은 사다리를 두 사람이 찾았다면 사다리를 앞에서부터 한 단어씩 비교한다. 처음으로 달라지는 자리에서 사전순으로 앞서는 단어를 쓴 사람이 이긴다. 위의 두 사다리를 비교하면 CORD가 WOLD보다 앞서므로 첫 번째 사다리가 이긴다.

미니언 Kevin은 사전을 하나 정해 놓고 논다. 사다리에 쓰는 단어는 양 끝의 두 단어까지 포함해 모두 그 사전에 있어야 한다. 두 단어는 길이가 같고 정확히 한 자리만 다를 때에만 이웃이다. 길이가 다른 두 단어는 이웃이 아니다. Kevin이 이길 수 있도록 단어 쌍마다 사다리를 찾아라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 사전 하나와 단어 쌍의 목록으로 이루어진다. 먼저 사전에 든 단어의 수 $N$이 주어지고, 이어서 단어 $N$개가 주어진다. 그다음 사다리를 찾아야 하는 쌍의 수 $Q$가 주어지고, 이어서 쌍 $Q$개가 주어진다. 쌍 하나는 단어 두 개다.

모든 수와 단어는 공백이나 줄바꿈으로 구분되고, 줄을 나누는 방식은 정해져 있지 않다. 단어는 영어 소문자로만 이루어진다(Gru가 아니라 gru).

• $1 \le T \le 9$
• $1 \le N \le 1000$
• $1 \le Q \le 20$
• 단어의 길이는 $1$ 이상 $10$ 이하다.
• 한 사전 안의 단어는 서로 다르다.
• 각 쌍의 두 단어는 모두 그 사전에 들어 있다.

쌍마다 입력에 주어진 순서대로 한 줄씩 출력한다.

사다리가 있으면 다음 형식으로 출력한다.

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

$A$는 쌍의 첫 단어, $B$는 둘째 단어이고 $w_1, \dots, w_k$는 사다리를 이루는 단어다. 단어 수가 가장 적은 사다리를 출력하고, 그런 사다리가 여럿이면 단어 나열이 사전순으로 가장 앞서는 것을 출력한다. 사다리의 단어는 -->(공백, 하이픈 두 개, >, 공백)로 잇는다.

사다리가 없으면 다음을 출력한다.

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

$A$와 $B$가 같은 단어이면 사다리는 그 단어 하나뿐이므로 Word ladder from A to A: A 형태가 된다.