当前没有测试数据。

字典 wordList 中从单词 beginWord​ ​到 endWord 的 转换序列 ​是一个按下述规格形成的序列 beginWord -> s₁ -> s₂ -> ... -> s_k：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 s_i都在wordList中。注意，beginWord​ ​不需要在 wordList 中。
• s_k == endWord

给你两个单词​ ​beginWord​ ​和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

输入格式

第一行一个字符串$s1$，表示beginWord。 第二行一个字符串$s2$，表示endWord。 第三行输入n 第四行输入n个字符串

输出格式

输出一行，表示最短转换序列 中的 单词数目*

样例1

hit
cog
6
hot dot dog lot log cog

5

样例2

hit
cog
5
hot dot dog lot log

0

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord和 wordList[i]由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同