Word Ladder Transformation

In this problem, you are given two words, begin_word and end_word, along with a list of words word_list. Your task is to find the length of the shortest transformation sequence from begin_word to end_word under the following rules:

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

The transformation sequence length is defined as the number of words in the sequence including the begin and end words. If it is not possible to transform begin_word into end_word, output -1.

Formally, if we denote the transformation as a function, we wish to compute:

\[ \min\{ steps \mid begin\_word \to \ldots \to end\_word \} \]

Note that if begin_word is equal to end_word, the answer is 1.

inputFormat

The input is given via standard input (stdin) with the following format:

begin_word end_word
n
word1 word2 ... wordn

Where begin_word and end_word are strings, n is an integer representing the number of words in the word list, followed by n words separated by spaces.

outputFormat

Output a single integer on standard output (stdout) representing the minimum number of transformation steps from begin_word to end_word. If no such transformation exists, output -1.

## sample

hit cog
6
hot dot dog lot log cog

5