Time limit: 1 second

Memory limit: 256 megabytes

题目描述

源神 在玩 Wordle 的时候爱查字典，但是老是猜不准，而且经常只能猜中一个位置，所以 源神 自己做了另一款游戏 —— Another Wordle。

因为不喜欢频繁翻找字典，源神 的 Another Wordle 替你把字典准备好了。

Another Wordle 会给你一个大小为 $n$ 的字典，其中包含了长度为 $m$ 的 $n$ 个字符串。

然后再给你两个长度为 $m$ 的单词 $s$ 和 $t$ ，注意 $s$ 和 $t$ 可能 不被 包含在字典当中。

然后你需要根据一下的变换规则，将 $s$ 变换为 $t$：

• 每次变换形成的新字符串必须包含在字典当中
• 每次变换只能修改一个位置的字符，如：genshin 修改为 genshim

在经过若干次变换之后，如果 $s$ 能变换为 $t$，我们的目的则是求出最小的变换序列所包含的单词数目，如果 $s$ 不能变换为 $t$，则输出 $-1$。

输入

第一行包含两个整数 $n$ 和 $m$。

接下来 $n$ 行包含 $n$ 个长度为 $m$ 的字符串，代表字典中的字符串。

最后两行包含两个字符串，代表 $s$ 和 $t$。

输出

如果 $s$ 能变换为 $t$，则输出最小的变换序列所包含的单词数目，如果不能，则输出 $-1$。

限制

$1 \le n \le 5000$, $1 \le m \le 10$

保证字典中的字符串互不相同。

$s$、$t$、字典中的字符串均由小写英文字母组成。

$s \neq t$

6 3
got
aot
aog
bot
bog
dog
git
dog

5

样例解释

一个最短转换序列是 "git" $\rightarrow$ "got" $\rightarrow$ "aot" $\rightarrow$ "aog" $\rightarrow$ "dog", 返回单词数量 $5$。