G: Careful Teacher |
Once upon a time there was a teacher that wanted to teach his students all the words in the dictionary. To do so, he started selecting by memory two words of the dictionary, and wanted their students to be changing the leters of the words, one by one, so that the original word eventually got converted into the final word, but with the restriction that every step only a letter could be changed, and, very importantly, each intermediate word must also be part of the dictionary.
You have to help the teacher to know beforehand if a word can be changed into another word, one letter at a time, and each intermediate word belonging to a given dictionary, so that the teacher can select interesting examples to his students.
Your program receives a list of (different) words, one each line,
forming the dictionary, a line to end the dictionary, with the
characters "--
", and several lines, each
containing two words separated by a space (starting word and ending
word, respectively). For each pair, you have to tell if the first
word can be converted into the second using the given
dictionary. The dictionary will have fewer than 20000 words.
For each input word pair, your program must print "Yes" if the first word can be converted into the second, or "No" if it cannot be done.
abc abd acc bbb aba -- abc acc abc bbb acc abd bbb abc abd abc aba abc
Yes No Yes No Yes Yes