Shortest Word Ladder Length

Given a dictionary of words and two words, start and end, determine the length of the shortest transformation sequence from start to end such that:

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

If the start word is the same as the end word then the answer is 1, and if no valid transformation sequence exists, output -1.

Note: The transformation does not require the start word to be in the dictionary. All words (including start and end) are assumed to be of the same length.

inputFormat

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

N
word1 word2 ... wordN
start
end

Where:

• N is an integer representing the number of words in the dictionary.
• The next line contains N space-separated words.
• The following line contains the start word.
• The last line contains the end word.

outputFormat

Output the length of the shortest transformation sequence from start to end to standard output (stdout). If no such transformation exists, output -1.

## sample

5
hot dot dog lot log
hot
dog

3