5653 - 提高:广搜优化:双向BFS:字符串变化

通过次数

3

提交次数

100

Time Limit : 1 秒
Memory Limit : 128 MB

给定两个字符串 a 和 b,以及一个单词字典。你需要找到将 a 转换为 b 的最短步骤数。每一步只能修改一个字符,且修改后的字符串必须存在于字典中。 如果找不到解则输出-1

Input

第一行2各字符串,中间1个空格隔开 之后若干行,每行一个字符串

Output

输出1个整数,含义如题干所示

Examples

Input

hit cog
hot
dot
dog
lot
log
cog

Output

4

Hint

解释: hit -> hot -> dot -> dog -> cog ,共4步。