Doublets

A doublet is a pair of words that differ in exactly one letter; for example, "booster" and "rooster", or "rooster" and "roaster", or "roaster" and "roasted".

You are given a dictionary of up to $25143$ lowercase words, each at most $16$ letters long. You are then given several pairs of words. For each pair, find the shortest sequence of words that begins with the first word and ends with the second, so that every pair of adjacent words in the sequence is a doublet. For example, for the pair "booster" and "roasted", one such sequence is ("booster", "rooster", "roaster", "roasted"), provided that all of these words appear in the dictionary.

The input begins with the dictionary: a number of words, one per line, terminated by an empty line. The word pairs follow, one pair per line, with the two words separated by a single space.

For each pair, print the shortest sequence of words on separate lines, beginning with the first word and ending with the second, so that every pair of adjacent lines is a doublet.

If several shortest sequences exist, print the lexicographically smallest one: compare the candidate sequences word by word starting from the first word, and choose the sequence whose first differing word is smallest.

If no such sequence exists, print a single line containing No solution. Leave one blank line between the outputs of consecutive pairs.