6762: Word
[Creator : ]
Description
给你一个包含 $n$ 个单词的单词表。你需要将单词 $s$ 以如下操作转换成 $t$。
每次改变 $s$ 的一个字母。你需要保证改变后的 $s=t$ 或在单词表中出现过。询问最小操作次数并输出方案。如果不能将 $s$ 变成 $t$，输出 $-1$。
Input
第一行两个正整数 $n,m$，表示单词表共 $n$ 个单词，每个单词的长度都为 $m$。
接下来第 $2 \sim n+1$ 行每行一个长度为 $m$ 的字符串，表示单词表中的第 $i$ 个单词。
最后一行两个长度为 $m$ 的字符串 $s,t$，含义如题目描述。
接下来第 $2 \sim n+1$ 行每行一个长度为 $m$ 的字符串，表示单词表中的第 $i$ 个单词。
最后一行两个长度为 $m$ 的字符串 $s,t$，含义如题目描述。
Output
第一行一个整数，表示最小操作次数。
假设你输出的最小操作次数为 $st$，操作方案输出方案如下：
方案共包含 $st+2$ 行，每行输出一个字符串表示每步转换后的字符串 $s$。你需要保证第一行的字符串是 $s$ 且最后一行的字符串是 $t$。
假设你输出的最小操作次数为 $st$，操作方案输出方案如下：
方案共包含 $st+2$ 行，每行输出一个字符串表示每步转换后的字符串 $s$。你需要保证第一行的字符串是 $s$ 且最后一行的字符串是 $t$。
注意把某个字符串变成最终答案 $t$ 的操作不计入 $st$。
Constraints
对于 $100\%$ 的数据，$1 \le n \le 2000,\ 1 \le m \le 20$。
Sample 1 Input
5 3
qwq
awa
qwa
pwq
abc
qaq aww
Sample 1 Output
3
qaq
qwq
qwa
awa
aww
Sample 2 Input
2 2
qw
wq
bb bb
Sample 2 Output
0
bb
bb
Sample 3 Input
3 2
bf
ab
fg
aa cd
Sample 3 Output
-1