4440 - 词链

如果单词 X 的末字母与单词 Y 的首字母相同，则 X 与 Y 可以相连成 X.Y。（注意：X、Y 之间是英文的句号 .）。例如，单词 dog 与单词 gopher，则 dog 与 gopher 可以相连成 dog.gopher。

另外还有一些例子：

• dog.gopher
• gopher.rat
• rat.tiger
• aloha.aloha
• arachnid.dog

连接成的词可以与其他单词相连，组成更长的词链，例如：

aloha.arachnid.dog.gopher.rat.tiger

注意到，. 两边的字母一定是相同的。

现在给你一些单词，使得词链尽可能的长，使得每个单词在词链中最多出现且仅出现一次。注意，相同的单词若出现了 k 次就最多输出 k 次。

第一行是一个正整数 n（1 \le n \le 20），代表单词数量。

接下来共有 n 行，每行是一个由 1 到 20 个小写字母组成的单词。

只有一行，表示组成字典序最小的词链 。保证答案唯一

• 对于 100\% 的数据，有 n \leq 30。

原创