Minimum Word Transformation

You are given two words: an initial word and a target word, along with a list of valid words called the dictionary. Your task is to determine the minimum number of transformations needed to convert the initial word into the target word.

In one transformation, you can change exactly one letter of the word, and the resulting word must be in the given dictionary. Note that the transformation process can be visualized as a path, where each edge represents a valid transformation. In particular, if two words differ in exactly one letter, then they are considered adjacent. Formally, for two words \(w_1\) and \(w_2\) of equal length, the condition for a valid single transformation is:

[ \text{diff}(w_1, w_2) = 1, ]

If no such transformation sequence exists, return -1. If the initial word is the same as the target word, the answer is 0.

Read the input from standard input (stdin) and print the result to standard output (stdout).

inputFormat

The input is given via stdin in the following format:

1. A string representing the initial word.
2. A string representing the target word.
3. An integer \(n\) representing the number of words in the dictionary.
4. A single line containing \(n\) space-separated words which represent the dictionary.

Note: All words are guaranteed to be of the same length.

outputFormat

Output a single integer to stdout representing the minimum number of transformations required to convert the initial word to the target word. If the transformation is impossible, output -1.

## sample

hit
cog
6
hot dot dog lot log cog

4