问题描述

在欧洲有一个著名的文字游戏叫做“Dublette”。这个游戏的规则是通过逐个变换字母将一个单词转化为另一个单词。例如，将 head 转化为 tail，需要经过 4 个单词的变换：head→heal→teal→tell→tall→tail。编写一个程序，在给定的单词列表中执行 Dublette，并显示变换过程。要求变换次数最少。

输入

从标准输入中以以下格式给出输入：

$first$ $last$

$N$

$s_{0}$

$s_{1}$

:

$s_{N-1}$

1. 第 1 行包含初始单词 $first$ 和目标单词 $last$，两者之间用一个空格分隔。
2. 第 2 行包含单词列表的大小 $N (1≦N≦1,000)$。
3. 第 3 到第 $N+2$ 行依次给出单词列表中的 $N$ 个单词。

• 单词列表中可能包含重复的单词，且最初的单词 $first$ 和目标单词 $last$ 可能出现在单词列表中。
• 但是，最初的单词 $first$ 和目标单词 $last$ 可能相同。
• 每个单词的长度都相等，介于 1 到 30 之间。
• 每个单词只由小写英文字母 a-z 构成。

输出

如果可以进行变换，则输出第一行为变换所使用的单词个数 $k$，下面的 $k+2$ 行依次输出包括初始单词和目标单词的变换过程。每行只输出一个单词。如果存在多个变换过程，可以随意选择一个进行输出。如果初始单词和目标单词相同，则输出 $k=0$。如果无法进行变换，则输出 -1。输出结束后要换行。

示例 1

输入示例

eye lid
4
lie
die
did
dye

输出示例

3
eye
dye
die
lie
lid

1. 第一行输出变换所使用的单词数 $k$，这里为 3。
2. 从第二行开始，依次输出变换过程。

• eye ... 是初始单词 $first$。
• dye ... 将 eye 的第一个字母 e 变换为 d。
• die ... 将 dye 的第二个字母 y 变换为 i。
• lie ... 将 die 的第一个字母 d 变换为 l。
• lid ... 将 lie 的第三个字母 e 变换为 d，同时是最后的目标单词 $last$，所以停止变换。

示例 2

输入示例

eye eye
4
lie
die
did
dye

输出示例

0
eye
eye

• 初始单词 $first$ 和目标单词 $last$ 相同，所以变换所使用的单词数 $k=0$。
• 分别输出初始单词 $first$ 和目标单词 $last$，每个单词占一行，然后结束。

示例 3

输入示例

eye lid
4
lie
lip
did
dye

输出示例

-1

• 由于给定的单词列表无法将 eye 转换为 lid，所以输出 -1。