Word Ladder Transformation

You are given two words: a start word and an end word, along with a dictionary of allowed words. Your task is to determine the length of the shortest transformation sequence from the start word to the end word such that:

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

For example, given start = "hit", end = "cog" and dictionary ["hot", "dot", "dog", "lot", "log", "cog"], one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog" with a length of 5. If no valid transformation exists, output 0. All transformations must obey the rule that exactly one letter is changed during each step.

Note: The transformation sequence includes the start word and the end word. If the start word is the same as the end word, the sequence length is 1.

inputFormat

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

1. The first line contains a string representing the start word.
2. The second line contains a string representing the end word.
3. The third line contains an integer n, representing the number of words in the dictionary.
4. The following n lines each contain one dictionary word.

All words are assumed to have the same length.

outputFormat

Output a single integer to stdout which represents the length of the shortest transformation sequence from the start word to the end word. If no valid transformation exists, output 0.

hit
cog
6
hot
dot
dog
lot
log
cog

5