Word Ladder Transformation Sequence

Given two words, beginWord and endWord, and a dictionary of words, your task is to determine the length of the shortest transformation sequence from beginWord to endWord. Each transformation must change exactly one letter at a time, and every intermediate word must exist in the given dictionary.

A valid transformation sequence is defined as:

[ w_{1}, w_{2}, \ldots, w_{n} ]

where:

• w₁ = beginWord
• w_n = endWord
• For each i (1 \leq i < n), w_i and w_i+1 differ by exactly one letter.

If no such transformation sequence exists, output 0.

Note: If endWord is not present in the dictionary, no valid transformation is possible.

inputFormat

The input is read from stdin and is in the following format:

beginWord endWord
n
word_1
word_2
... 
word_n

Where:

• beginWord and endWord are the starting and target words respectively.
• n is the number of words in the dictionary.
• Each of the next n lines contains a word in the dictionary.

outputFormat

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

## sample

hit cog
6
hot
dot
dog
lot
log
cog

5