더블릿

더블릿(doublet) 은 정확히 한 글자만 다른 두 단어의 쌍입니다. 예를 들어 "booster"와 "rooster", "rooster"와 "roaster", "roaster"와 "roasted"는 각각 더블릿입니다.

각 단어의 길이가 최대 $16$글자인 소문자 단어 최대 $25143$개로 이루어진 사전이 주어집니다. 이어서 여러 개의 단어 쌍이 주어집니다. 각 쌍에 대해, 첫 번째 단어로 시작해서 두 번째 단어로 끝나며 인접한 두 단어가 항상 더블릿이 되는 가장 짧은 단어 수열을 찾으세요. 예를 들어 "booster"와 "roasted" 쌍이 주어지면, 이 단어들이 모두 사전에 있을 때 ("booster", "rooster", "roaster", "roasted")가 하나의 해가 됩니다.

입력은 사전으로 시작합니다. 사전은 한 줄에 한 단어씩 주어지며, 빈 줄로 끝납니다. 그 뒤로 단어 쌍들이 이어지며, 각 쌍의 두 단어는 한 줄에 공백 하나로 구분되어 주어집니다.

각 쌍에 대해, 첫 번째 단어로 시작해 두 번째 단어로 끝나고 인접한 두 줄이 항상 더블릿이 되는 가장 짧은 단어 수열을 한 줄에 한 단어씩 출력하세요.

가장 짧은 수열이 여러 개라면 사전순으로 가장 앞서는 것을 출력합니다. 즉, 첫 번째 단어부터 차례로 수열을 비교하여 처음으로 달라지는 단어가 가장 작은 수열을 고릅니다.

그런 수열이 없으면 No solution. 한 줄만 출력하세요. 연속한 두 쌍의 출력 사이에는 빈 줄을 하나 넣으세요.