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` 构成。