Word Ladder Transformation

You are given two words, a start word and an end word, and a dictionary of valid English words. Your task is to transform the start word into the end word using the following rules:

• Only one letter can be changed at a time.
• Each intermediate word in the transformation sequence must exist in the provided dictionary.

The transformation process is defined as follows: if the start word equals the end word, then the number of steps is 1. Otherwise, every valid transformation (changing one letter) counts as one step. If it is impossible to transform the start word into the end word using the given dictionary, output -1.

The answer should be computed as the minimum number of steps required, where the count starts at 1 with the start word.

Formally, if we denote a transformation by changing one letter (i.e., if words differ by exactly one letter), and let \( S \) be the starting word and \( E \) be the ending word, your task is to compute the minimum integer \( k \) such that there exists a sequence

\[ S = w_{1}, w_{2}, \dots, w_{k} = E \]

where for each \( 1 \le i < k \), \( w_{i} \) and \( w_{i+1} \) differ by exactly one letter and \( w_{i+1} \) is in the dictionary. If no such sequence exists, output \(-1\).

inputFormat

The input is read from standard input (stdin) and has the following format:

<start>
<end>
<n>
<word_1>
<word_2>
... 
<word_n>

where:

• <start> is a string denoting the start word.
• <end> is a string denoting the end word.
• <n> is an integer representing the number of words in the dictionary.
• The following n lines each contain a word from the dictionary.

outputFormat

The output is printed to standard output (stdout) as a single integer representing the minimum number of transformation steps required to convert the start word to the end word. If no valid transformation is possible, output -1.

## sample

hit
cog
6
hot
dot
dog
lot
log
cog

5