#P1127. 词链
词链
题目描述
如果单词 的末字母与单词 的首字母相同,则 与 可以相连成 。(注意:、 之间是英文的句号 .
)。例如,单词 dog
与单词 gopher
,则 dog
与 gopher
可以相连成 dog.gopher
。
另外还有一些例子:
dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog
连接成的词可以与其他单词相连,组成更长的词链,例如:
aloha.arachnid.dog.gopher.rat.tiger
注意到,.
两边的字母一定是相同的。
现在给你一些单词,请你找到字典序最小的词链,使得每个单词在词链中出现且仅出现一次。注意,相同的单词若出现了 次就需要输出 次。
输入格式
第一行是一个正整数 (),代表单词数量。
接下来共有 行,每行是一个由 到 个小写字母组成的单词。
输出格式
只有一行,表示组成字典序最小的词链,若不存在则只输出三个星号 ***
。
6
aloha
arachnid
dog
gopher
rat
tiger
aloha.arachnid.dog.gopher.rat.tiger
提示
- 对于 的数据,有 ;
- 对于 的数据,有 。