Word Morph

Farmer John is playing a word game against his cows. It goes like this:

• Farmer John first chooses a word, such as cat.
• The cows then choose their own word, perhaps dog.

Farmer John must then morph his word into the cows' word. He does this by repeatedly changing a single letter at a time to form a new valid word, where a valid word is any word contained in the dictionary given in the input.

For example, Farmer John could build the following sequence of words:

cat -> cot -> cog -> dog

morphing cat into dog in just three changes. The cows will never set an impossible task, so a morph always exists. Farmer John must get from his word to the cows' word in as few changes as possible.

Given a starting word and an ending word, determine and output the least number of single-letter changes needed to morph the starting word into the ending word. Each change alters exactly one letter, and the resulting word must also be in the dictionary.

• Line 1: an integer $N$, the number of words in the dictionary
• Next $N$ lines: one dictionary word per line
• Next line: the starting word
• Next line: the ending word

Every word consists of lowercase letters only. The starting and ending words are guaranteed to be in the dictionary, and a morph from the starting word to the ending word is guaranteed to exist.

• Line 1: a single integer, the least number of single-letter changes required to transform the starting word into the ending word.