A common word puzzle found in many newspapers and magazines is the word transformation. By taking a starting word and successively altering a single letter to make a new word, one can build a sequence of words which changes the original word to a given end word. For instance, the word ``spice'' can be transformed in four steps to the word ``stock'' according to the following sequence: spice, slice, slick, stick, stock. Each successive word differs from the previous word in only a single character position while the word length remains the same.
Given a dictionary of words from which to make transformations, plus a list of starting and ending words, your team is to write a program to determine the number of steps in the shortest possible transformation.
The input will be a single file in two sections. The first section will be the dictionary of available words with one word per line, terminated by a line containing an asterisk (*) rather than a word. There can be up to 200 words in the dictionary; all words will be alphabetic and in lower case, and no word will be longer than ten characters. Words can appear in the dictionary in any order.
Following the dictionary are pairs of words, one pair per line, with the words in the pair separated by a single space. These pairs represent the starting and ending words in a transformation. The pairs are terminated by the end-of-file. All pairs are guaranteed to have a transformation using the dictionary given. The starting and ending words will appear in the dictionary.
The output should contain one line per word pair, and must include the starting word, the ending word, and the number of steps in the shortest possible transformation, separated by single spaces.
(For those people who listen to National Public Radio (NPR), the Sunday morning broadcast Weekend Edition, Sunday usually has a word puzzle for the listening audience. Occasionally the puzzle is a transformation. NPR allows the submission of puzzle answers via e-mail, to the address wesun@npr.org. You can use this code to generate solutions to the transformation puzzles and possibly get a chance to be on the air for the live puzzle round.)
dip lip mad map maple may pad pip pod pop sap sip slice slick spice stick stock * spice stock may pod
spice stock 4 may pod 3