#P1127. 词链

词链

题目描述

如果单词 XX 的末字母与单词 YY 的首字母相同,则 XXYY 可以相连成 X.YX.Y。(注意:XXYY 之间是英文的句号 .)。例如,单词 dog 与单词 gopher,则 doggopher 可以相连成 dog.gopher

另外还有一些例子:

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

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

aloha.arachnid.dog.gopher.rat.tiger

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

现在给你一些单词,请你找到字典序最小的词链,使得每个单词在词链中出现且仅出现一次。注意,相同的单词若出现了 kk 次就需要输出 kk 次。

输入格式

第一行是一个正整数 nn1n10001 \le n \le 1000),代表单词数量。

接下来共有 nn 行,每行是一个由 112020 个小写字母组成的单词。

输出格式

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

6
aloha
arachnid
dog
gopher
rat
tiger
aloha.arachnid.dog.gopher.rat.tiger

提示

  • 对于 40%40\% 的数据,有 n10n \leq 10
  • 对于 100%100\% 的数据,有 n1000n \leq 1000