3044: 【提高+/省选-】【P1127】词链

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

如果单词 lns="http://www.w3.org/1998/Math/MathML">� 的末字母与单词 lns="http://www.w3.org/1998/Math/MathML">� 的首字母相同，则 lns="http://www.w3.org/1998/Math/MathML">� 与 lns="http://www.w3.org/1998/Math/MathML">� 可以相连成 lns="http://www.w3.org/1998/Math/MathML">�.�。（注意：lns="http://www.w3.org/1998/Math/MathML">�、lns="http://www.w3.org/1998/Math/MathML">� 之间是英文的句号 .）。例如，单词 dog 与单词 gopher，则 dog 与 gopher 可以相连成 dog.gopher。

另外还有一些例子：

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

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

aloha.arachnid.dog.gopher.rat.tiger

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

现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了 lns="http://www.w3.org/1998/Math/MathML">� 次就需要输出 lns="http://www.w3.org/1998/Math/MathML">� 次。

输入

第一行是一个正整数 lns="http://www.w3.org/1998/Math/MathML">�（lns="http://www.w3.org/1998/Math/MathML">1≤�≤1000），代表单词数量。

接下来共有 lns="http://www.w3.org/1998/Math/MathML">� 行，每行是一个由 lns="http://www.w3.org/1998/Math/MathML">1 到 lns="http://www.w3.org/1998/Math/MathML">20 个小写字母组成的单词。

输出

只有一行，表示组成字典序最小的词链，若不存在则只输出三个星号 ***。

样例输入 复制 

6
aloha
arachnid
dog
gopher
rat
tiger

样例输出 复制 

aloha.arachnid.dog.gopher.rat.tiger

提示

  • 对于 lns="http://www.w3.org/1998/Math/MathML">40% 的数据，有 lns="http://www.w3.org/1998/Math/MathML">�≤10；
  • 对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据，有 lns="http://www.w3.org/1998/Math/MathML">�≤1000。

来源/分类

提交提交记录统计露一手!