Problem I
Word Morphing
|
Orlando was looking at his soup while his
mother was in the kitchen. He was playing with the letters in his soup, and
suddenly, he noticed that had a secret power. He could change the words
morphing one word to another replacing the letter in a mysterious order.
Orlando has changed the letters of some words,
you have to find an algorithm that find out the morphing order from the
original word to the morphed one. The rules are simple:
1.- In each step you just can change one letter
from the previous word.
2.- A letter can be changed just once
3.- All the letters in the word must change.
The input is a file containing several unordered
morphing series. For each one you have a line with the number of words, the
number of letters in each word, next line is the first word, third line is
the morphed one. The rest are the intermediate words unordered. The number
of words are unlimited and all the words in each set have the same size. You
can assume that all the characters are letters (capital or not).
For each morphing you should print all the
words in the correct order to convert the first one in the morphed one
6 5
remar
pitos
remas
remos
retos
ritos
5 4
pato
lisa
pata
pita
pisa
remar
remas
remos
retos
ritos
pitos
pato
pata
pita
pisa
lisa