Дуплеты

Дублетом называются два слова, которые отличаются ровно в одной букве (например, «booster» и «rooster», или «rooster» и «roaster», или «roaster» и «roasted»).
Вам задается словарь длиной не более 25 143 слов, состоящих из строчных букв, причем длина каждого слова не превышает 16 букв. Далее вам задается некоторое число пар слов. Для каждой пары слов найдите последовательность слов, имеющую наименьшую длину, причем первое слово последовательности должно совпадать с первым словом из заданной пары, а последнее слово последовательности - со вторым словом из пары. Каждая пара соседних слов последовательности должна быть дублетом. Например, если вам задана пара «booster» и «roasted», возможным решением является «booster», «rooster», «roaster», «roasted», при условии, что все эти слова присутствуют в словаре.

Входные данные
Файл входных данных содержит словарь, за которым следует некоторое число пар слов. Словарь состоит из произвольного числа слов, по одному на строку, и завершается пустой строкой. Далее идут пары слов; каждая строка содержит пару слов, разделенных пробелом.

Выходные данные
Для каждой введенной пары напечатайте набор строк, начинающийся с первого слова и заканчивающийся последним. Каждая пара соседних строк должна быть дублетом.
Если существует несколько вариантов минимальных решений, то подойдет любое. Если решения не существует, выведите строку "No solution". Между блоками должна быть пустая строка.
Примеры входных данных:-----------------Соответствующие выходные данные:[/RIGHT]
Booster----------------------------------------booster
rooster-----------------------------------------rooster
roaster-----------------------------------------roaster
coasted----------------------------------------roasted
roasted
coastal-----------------------------------------No solution
postal

booster roasted
coastal postal