Word Transformation Sequence

You are given a start word, an end word, and a dictionary of valid 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 is changed at each step and each intermediate word must exist in the dictionary.

For each transformation, only one letter can be changed. Formally, if you have a word \(w = w_1w_2\cdots w_k\), you can change it to a word \(w' = w_1'w_2'\cdots w_k'\) if and only if there exists an index \(i\) such that \(w_i \neq w_i'\) and for every \(j \neq i\), \(w_j = w_j'\). If no such sequence exists, output -1.

Examples:

Input:
6
hit
cog
hot dot dog lot log cog
Output:
5

</p>

inputFormat

The input is given from the standard input (stdin) in the following format:

n
start
end
word1 word2 ... wordn

Where:

• n is the number of words in the dictionary.
• start is the starting word.
• end is the target word.
• The next line contains n words separated by spaces representing the dictionary.

outputFormat

Output a single integer representing the length of the shortest transformation sequence if one exists; otherwise, output -1.

## sample

6
hit
cog
hot dot dog lot log cog

5