Problem E
Word Morph

Given two words (e.g., food, gold) and a dictionary, find if you can morph the first word into the second word using valid words from the dictionary replacing one character at each step. Supposing that “food”, “good", and “gold” are in the dictionary, a valid morph from “food” to “gold” would be:

If more than one valid morph step is possible then the one that appears first in the dictionary is the one that should be used. In addition, an example of a failed morph would be the initial word “poor” and the target word “rich”, with the words “pooh”, “rick”, and “rich” as our dictionary. The morph would fail because the target word can not be reached:

However, we impose the following restriction: once a character morphs, that character can not morph again. For example, if the initial word is “hate” and the target word is “love” then the following morph is not valid (assuming that all words are in the dictionary), because the same letter position is morphed twice:

Notice, the first letter ‘h’ morphed twice, the first time it morphed to ‘d’ and then to ‘l’ in love. Therefore, this is not a valid morph.

Input

The first line contains the initial 4-letter word, and the second line contains the target 4-letter word. The third line contains the dictionary of 4-letter words separated by commas. No word will appear more than once in the dictionary. You can assume that the given words are valid with proper length and contain only lowercase letters.

Output

Your program should output the morph step number starting from zero, and on the same line the morphed word in each step. Each line represents a morph step with one letter morphed from the previous line. The goal is to have the last morph be the target word. If there is no valid morph between the two words, then “morph failed.” should be printed on a single line. Otherwise, your program should output “morph success!” after the sequence of words in the morph.

food
gold
food,good,gold,hold,told

initial: food
step 0 is: good
step 1 is: gold
morph success!

word
text
food,good,gold,hold,told,wort

morph failed.