Word Ladder Transformation Sequence

Given two words, (beginWord) and (endWord), and a dictionary (wordList), find the length of the shortest transformation sequence from (beginWord) to (endWord) such that only one letter can be changed at a time and each intermediate word must exist in (wordList). Each transformation must change exactly one character. For example, the transformation from "hit" to "cog" using the dictionary ["hot", "dot", "dog", "lot", "log", "cog"] has a shortest sequence length of 5. If no such transformation exists, output 0.

inputFormat

The input is read from standard input (stdin). The first line contains the string (beginWord). The second line contains the string (endWord). The third line contains an integer (n) denoting the number of words in the dictionary. The following (n) lines each contain a word from (wordList).

outputFormat

Output a single integer representing the length of the shortest transformation sequence from (beginWord) to (endWord), or 0 if no valid sequence exists.## sample

hit
cog
6
hot
dot
dog
lot
log
cog

5