BackGroud

FatMouse非常喜欢摆弄单词卡片。一天,它发明了一个非常好玩的游戏:单词梯子。 FatMouse很快就喜欢上了这个游戏,并且对它爱不释手,以至于到了后来是废寝忘食。眼看着FatMouse一天天瘦下去将变成ThinMouse,你决定帮助它,要让它停止玩这个游戏,多吃点东西,以保持它健壮的身体。于是,首先,你开始钻研起这个游戏来...

The Problem

在Mouse的世界里,它们认为如果两个单词只相差一个字母,那么这两个单词就是相邻的。FatMouse发明的游戏是这样的,在一堆单词里面,随意找出两个单词,作为一个队列的头和尾。剩下要做的工作就是用剩下的单词填好这个队列,使队列中相邻的两个单词互相只相差一个字母,而且队列的长度尽可能短。如先选中cat和dog,那么可以找到这样一个序列:cat cot cog dog

输入

本题只包括一组输入数据,输入数据的第一行是两个整数n和m(n<=200,1<=m<10),n代表你所能选择的所有单词数。接下来是n个长度相等的单词,所有单词的长度均为4。待选单词输入完后接下来的,就是m对游戏中队列的头和尾代表的单词。可以保证一定能找到连续序列满足条件。

输出

对于输入中的每一对单词头和单词尾,输出最短的满足题意的单词序列。注意每行最后一个单词后没有空格,最后一组输出序列下面紧接着有一个空行。

样例输入

5 2
band
bard
card
hand
hard
band hard
card hand

样例输出

band bard hard
card hard hand


Author: 袁源 2003.4