Word Transformation Challenge

You are given a starting word and an ending word along with a list of available words. Your task is to find the length of the shortest transformation sequence from the starting word to the ending word 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 sequence, output 0. Note that the starting word might not be in the word list. The transformation sequence length is defined as the total number of words in the sequence including the start and the end words.

The transformation from word $w_1$ to $w_k$ is valid if and only if for each adjacent pair $w_i$ and $w_{i+1}$ (for $1 \le i < k$), they differ in exactly one character. Formally, if $w_i, w_{i+1} \in \text{wordList}$ (or for the start word, if it is not in the list), then:

\[ \text{diff}(w_i, w_{i+1}) = 1 \]

Your solution should read the input from stdin and output the result to stdout.

inputFormat

The input will be given in the following format:

start
end
n
word_1
word_2
... 
word_n

Where:

• start is the starting word.
• end is the target word.
• n is the number of words in the word list.
• Each of the next n lines consists of a word available for transformation.

outputFormat

Output a single number representing the length of the shortest transformation sequence from start to end. Output 0 if no such transformation sequence exists.

## sample

hit
cog
6
hot
dot
dog
lot
log
cog

5