Word Transformation

In this problem, you are given a starting word, a target word, and a dictionary of valid words. Your goal is to determine the minimum number of transformations needed to change the starting word into the target word. In each transformation, you can change exactly one letter of the current word, and the resulting word must be either the target word or a word from the dictionary. Note that if the starting word is the same as the target word, no transformation is needed.

The key idea is to use a breadth-first search (BFS) algorithm to explore all possible one-letter transformations. For a given word of length (L), there are at most (26 \times L) possible new words (each letter in the word can be replaced by any of the 26 letters). Your task is to find the shortest transformation sequence from the start word to the target word, where the number of transformations is minimal. The transformation condition is given by (\text{diff}(w_1, w_2) = 1), meaning exactly one letter difference between two words.

inputFormat

The input will be read from standard input (stdin) and has the following format:

1. The first line contains an integer (n) representing the number of words in the dictionary.
2. The second line contains the starting word.
3. The third line contains the target word.
4. The next (n) lines each contain a word from the dictionary.

All words will have the same length.

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of transformations required to convert the starting word into the target word. If it is not possible to transform the starting word into the target word using the dictionary, print -1.## sample

5
hit
cog
hot
dot
dog
lot
log

4