题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们已知一组单词 wordList，且给你一个开始单词 beginWord 和一个结束单词 endWord。单词 beginWord 和 endWord 之间的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 每次转换得到的单词必须是字典 wordList 中的单词。

请你找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

输入格式

输入的第一行为一个单独的整数 $n$ 表示字典 wordList 中的单词数，以下 $n$ 行每行有一个单词；

接下来两行分别输入两个单词 beginWord 和 endWord。

输出格式

输出一个整数表示从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，输出 $0$。

样例

6
hot
dot
dog
lot
log
cog
hit
cog

5

解释#1

一个最短转换序列是 hit -> hot -> dot -> dog -> cog, 它的长度为 5。

5
hot
dot
dog
lot
log
hit
cog

0

解释#2

cog 不在字典中，所以无法进行转换。

数据范围/约定

• beginWord、endWord 以及字典 wordList[i] 中的单词长度相等，并且长度不超过 $20$
• 字典中的单词数量不超过 $5000$
• beginWord、endWord 和 wordList[i] 均由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同