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. 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.
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. 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.