Word Ladder Transformation

You are given two words (a start word and an end word) and a dictionary of words. In each transformation step, you may change exactly one letter of the current word and the resulting word must exist in the dictionary. Your task is to find the length of the shortest transformation sequence from the start word to the end word.

The transformation sequence is defined as a sequence of words where the first word is the start word and the last word is the end word, and each adjacent pair of words differs by exactly one letter. The sequence length is defined as the number of words in the sequence.

In mathematical terms, if we denote the transformation sequence as $w_1, w_2, \dots, w_k$ with $w_1 = \text{start}$ and $w_k = \text{end}$ and for any $1 \leq i < k$, $w_{i+1}$ differs from $w_i$ by exactly one character, then your goal is to determine the minimum possible $k$. If there is no such sequence, output 0.

inputFormat

The input is read from standard input (stdin) and consists of multiple lines.

The first line contains two space-separated strings representing the start word and the end word.
The second line contains an integer $N$, the number of words in the dictionary.
Each of the following $N$ lines contains one word from the dictionary.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of transformations needed to convert the start word into the end word. If no such transformation sequence exists, output 0.## sample

hit cog
6
hot
dot
dog
lot
log
cog

5