Word Ladder Transformation

You are given two words, start and end, and a dictionary of words. Your task is to find the shortest transformation sequence from start to end such that only one letter can be changed at a time and each transformed word must exist in the dictionary.

If no such transformation exists, output 0. Note that the start word does not need to be in the dictionary, but each intermediate word must be.

The transformation sequence length is defined as the number of words in the sequence including the start and end words. For example, if the sequence is \(hit \to hot \to dot \to dog \to cog\), its length is 5.

The problem can be formally defined by the equation:

\[ \text{result} = \min_{\substack{w_0 = start,\ w_k = end\\ \forall i,\, w_{i}\text{ and }w_{i+1}\text{ differ by exactly one letter}}} k+1 \]

inputFormat

The input is given from standard input and consists of multiple lines:

• The first line contains the starting word.
• The second line contains the target word.
• The third line contains an integer \(N\), indicating the number of words in the dictionary.
• The next \(N\) lines each contain one word from the dictionary.

outputFormat

Output a single integer representing the length of the shortest transformation sequence from start to end. If no such sequence exists, output 0.

## sample

hit\ncog\n6\nhot\ndot\ndog\nlot\nlog\ncog

5