AT_arc011_3.[ARC011C] ダブレット

你正在玩一个单词接龙游戏。

一个单词可以变换为另一个单词，当且仅当这两个单词恰有一个字母不同。

给定起始单词 $first$ 和目标单词 $last$，以及一个含有 $N$ 个单词的 可重 词集 $\{s_0,s_1,...,s_{N-1}\}$。请回答，在只使用词集中的词进行变换的情况下，从 $first$ 变换到 $last$ 最少需要多少步 （所使用的词集中的词的个数），并给出一组方案。

特别地：

• 若 $first$ 和 $last$ 相同，则步数为 $0$；
• 若无法完成变换，仅输出一行 -1 即可；
• 若 $first$ 只经过一次变换即可得到 $last$，则步数也为 $0$。（这段话原题没写）

第一行输入两个单词 $first$ 和 $last$。

第二行输入一个正整数 $N$，表示词集大小。

第三行到第 $(N+2)$ 行，每行输入一个单词 $s_i$ 表示词集中的一个词。

若无法完成变换，仅输出一行一个整数 -1。

否则，按如下格式输出：

• 第一行输出一个整数 $k$，表示中间词的个数；
• 接下来 $(k+2)$ 行，每行一个单词。这 $(k+2)$ 行展示的即为从 $first$ 变换至 $last$ 的一种可能的过程。

若有多解，输出任一解即可。

输出末尾换行。

输入输出样例

输入 #1

eye lid
4
lie
die
did
dye

输出 #1

3
eye
dye
die
lie
lid

输入 #2

eye eye
4
lie
die
did
dye

输出 #2

0
eye
eye

输入 #3

eye lid
4
lie
lip
did
dye

输出 #3

-1

• $1\le N\le 1\ 000$；
• 词集中可能含有重复的单词，也可能含有 $first$ 和 $last$；
• 输入的每个单词长度都相同，且该长度 $L$ 满足 $1\le L\le 30$；
• 每个单词仅由英文小写字母 a-z 构成。