Word Ladder Transformation

You are given a word ladder problem: transform a start word into an end word by changing only one letter at a time. Each transformation must be a word present in a given word list. The transformation sequence should be as short as possible.

Formally, given two words, startWord and endWord, and an integer n representing the number of words in the dictionary, followed by n words, you are to determine the length of the shortest transformation sequence from startWord to endWord. If no such transformation exists, output 0.

The transformation rule is: in each step, you may only change one letter of the word, and the new word must exist in the dictionary. Note that the same word may not be used twice in the sequence.

The transformation length is defined as the number of words in the sequence including both the start and end words. For example, if the sequence is:

$$\text{hit} \to \text{hot} \to \text{cot} \to \text{cog}, $$

then the length is 4.

inputFormat

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

1. First line: a string representing startWord.
2. Second line: a string representing endWord.
3. Third line: an integer n, the number of words in the dictionary.
4. Next n lines: each line contains one word from the dictionary.

All words have the same length and consist of lowercase letters.

outputFormat

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

## sample

hit
cog
6
hot
dot
dog
lot
log
cog

5