Hide

Problem H
Doublets

Languages en es fr pt

Um doublet é um par de palavras que têm uma única letra diferente; por exemplo “booster” e “rooster”; “rooster” e “roaster”; ou “roaster” e “roasted”.

Você receberá um dicionário com até $25\, 143$ palavras em minúsculas. Nenhuma delas terá mais de $16$ letras. Você receberá vários pares de palavras. Para cada par de palavras, encontre a sequência mais curta de palavras que comece com a primeira palavra e termine com a segunda, de modo que cada par de palavras adjacentes seja um doublet. Por exemplo, se você receber o par “booster” e “roasted”, uma solução possível seria: (“booster”, “rooster”, “roaster”, “roasted”) desde que todas essas palavras estejam no dicionário.

Entrada

A entrada consiste no dicionário (com no máximo $25\, 143$ palavras) seguido por vários pares de palavras (no máximo $10$). O dicionário consiste em várias palavras, uma por linha, com uma linha em branco no final. Os pares de entrada de palavras se seguem; as palavras de cada par estão em uma linha, separadas por um espaço.

Saída

Para cada par de entrada, escreva um conjunto de linhas começando com a primeira palavra e terminando com a última. Cada par de linhas adjacentes deve ser um doublet. Se houver várias soluções mínimas, basta uma. Se não houver uma solução, simplesmente escreva na linha: “No solution.” Deixe uma linha em branco entre os casos.

Exemplo de entrada 1 Exemplo de saída 1
booster
rooster
roaster
coasted
roasted
coastal
postal

booster roasted
coastal postal
booster
rooster
roaster
roasted

No solution.