Problem B
Doublets

Un Doublet est une paire de mots dont la différence est d’une lettre au maximum ; par exemple, «booster» et «rooster» ou «rooster» et «roaster» ou «roaster» et «roasted».

Vous recevez un dictionnaire de $25143$ mots écrits en minuscules, ne dépassant pas $16$ lettres chacun. Vous recevez ensuite un certain nombre de paires de mots. Pour chaque paire de mots, trouvez la séquence de mots la plus courte qui commence par le premier mot et se termine par le second, de sorte que chaque paire de mots adjacents soit un doublet. Par exemple, si l’on vous attribuait la paire d’entrées «booster» et «roasted», une solution possible serait : («booster», «rooster», «roaster», «roasted») à condition que ces mots soient tous dans le dictionnaire.

Entrée

Une entrée se compose du dictionnaire (avec au plus $25143$ mots) suivi d’un certain nombre de paires de mots (au plus dix). Le dictionnaire se compose d’un certain nombre de mots, un par ligne, et se termine par une ligne vide. Les paires de mots d’entrée suivent ; les mots de chaque paire apparaissent sur une ligne, séparés par un espace.

Sortie

Pour chaque paire d’entrée, imprimez un ensemble de lignes commençant par le premier mot et se terminant par le dernier. Chaque paire de lignes adjacentes doit être un doublet. S’il existe plusieurs solutions minimales, n’importe laquelle fera l’affaire. S’il n’y a pas de solution, imprimez une ligne: «No solution.» Laissez une ligne vide entre les cas.

booster
rooster
roaster
coasted
roasted
coastal
postal

booster roasted
coastal postal

booster
rooster
roaster
roasted

No solution.