本题没有可用的提交语言。

题目描述

**双联词（Doublet）**是指一对仅有一个字母不同的单词；例如：

• "booster" 和 "rooster"
• "rooster" 和 "roaster"
• "roaster" 和 "roasted"

给定一个最多包含 25143 个小写单词的字典，每个单词不超过 16 个字母。然后给定若干对单词。对于每对单词，找到从第一个单词开始到第二个单词结束的最短单词序列，使得相邻的每对单词都是双联词。例如，如果输入单词对是 "booster" 和 "roasted"，一个可能的解是：
$("booster", "rooster", "roaster", "roasted")$
前提是这些单词都在字典中。

输入格式

输入由字典和若干对单词组成。字典部分由若干行单词组成，每行一个单词，以空行结束。随后是若干对输入单词，每对单词占一行，两个单词之间用空格分隔。

输出格式

对于每对输入单词，输出从第一个单词到最后一个单词的序列，每行一个单词。相邻的两行必须构成双联词。如果有多个最短解，输出任意一个即可。如果没有解，输出一行："No solution."。不同测试用例之间用空行分隔。

输入样例 1

booster
rooster
roaster
coasted
roasted
coastal
postal

booster roasted
coastal postal

输出样例 1

booster
rooster
roaster
roasted

No solution.

题目来源

Waterloo local 1999.01.31