词链

题目描述

如果单词$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` 注意到,“.”两边的字母一定是相同的。 现在给你一些单词,请你找到字典序最小的词链,使得这些单词在词链中出现且仅出现一次。

输入输出格式

输入格式


第一行是一个正整数$n(1 \le n \le 1000)$,代表单词数量。 接下来共有$n$行,每行是一个由$1$到$20$个小写字母组成的单词

输出格式


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

输入输出样例

输入样例 #1

6
aloha
arachnid
dog
gopher
rat
tiger

输出样例 #1

aloha.arachnid.dog.gopher.rat.tiger

说明

对于$40\%$的数据,有$n≤10$; 对于$100\%$的数据,有$n≤1000$。