GraphBFSString
Transform a begin word into an end word by changing exactly one letter at a time. Every intermediate word (and the end word) must be in the given word list. Find the number of words in the shortest transformation sequence, counting the begin word and the end word, or 0 if no sequence exists.
Input
Line 1: the begin word and the end word. Line 2: m, the size of the word list. Line 3: the m words. All words have the same length and contain lowercase letters.
Output
Print the length of the shortest sequence, or 0.
Constraints
1 <= word length <= 5 1 <= m <= 500 The begin word is different from the end word and need not be in the list.
Example 1
Input
hit cog 6 hot dot dog lot log cog
Output
5
hit -> hot -> dot -> dog -> cog has 5 words.
Example 2
Input
hit cog 5 hot dot dog lot log
Output
0
cog is not in the list, so no sequence exists.