Word Ladder Transformation

You are given two words, beginWord and endWord, and a list of words. Your task is to find the length L of the shortest transformation sequence from beginWord to endWord such that:

• Only one letter can be changed at a time.
• Each intermediate word must exist in the given word list.

If there is no such transformation, output 0. Note that if beginWord is the same as endWord, then L=1.

The transformation sequence has the form:

\( beginWord \rightarrow word_1 \rightarrow word_2 \rightarrow \cdots \rightarrow endWord \)

Your solution must read input from stdin and write the result to stdout.

inputFormat

The input is given from stdin in the following format:

<beginWord> <endWord>
<n>
<word_1>
<word_2>
...
<word_n>

where:

• beginWord and endWord are the starting and ending words respectively (separated by a space).
• n is an integer representing the number of words in the word list.
• Each of the next n lines contains a word from the word list.

outputFormat

Output a single integer to stdout denoting the length of the shortest transformation sequence from beginWord to endWord. If no transformation is possible, output 0.

## sample

hit cog
6
hot
dot
dog
lot
log
cog

5