问题描述

在这个问题中，给定一个由小写字母组成的单词列表。从这个列表中，找到最长的单词链 $w₁, ..., wₙ$，使得 $wᵢ$ 是 $wᵢ₋₁$ 的“混合扩展”$（mixed extension）$。一个单词 $A$ 是另一个单词 $B$ 的“混合扩展”，如果 $A$ 可以通过在 $B$ 中添加一个字母并重新排列结果得到。例如，$"ab"$, $"bar"$, $"crab"$, $"cobra"$, 和 $"carbon"$ 形成一个长度为 $5$ 的链。

输入

输入包含至少两行，但不超过 10000 行。每行包含一个单词。每个单词的长度至少为 1，且不超过 20。输入中的所有单词都是不同的。

输出

写出可以从给定单词中构造的最长链。将链中的每个单词单独输出在一行上，从第一个单词开始。如果有多个相同长度的最长链，输出其中任意一个即可。

示例输入 1

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc

示例输出 1

ab
bar
crab
cobra
carbon
carbons

来源

Rocky Mountain 2004