题目描述

如果单词 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≤n≤1000），代表单词数量。 接下来共有 n 行，每行是一个由 1 到 20 个小写字母组成的单词。

输出格式

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

样例

输入样例 1

6
aloha
arachnid
dog
gopher
rat
tiger

输出样例 1

aloha.arachnid.dog.gopher.rat.tiger

输入样例 2

7
aloha
arachnid
dog
gopher
rat
tiger
tiger

输出样例 2

***

输入样例 3

7
aloha
aloha
arachnid
dog
gopher
rat
tiger

输出样例 3

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

提示

思路：Hierholzer 算法找欧拉路径。 需要先[建模转化]为图。 本题建模方式：以单词为边，单词的首字母和末字母为点连边。 比如单词 abc，就是从顶点 a 指向顶点 c 的边之一。当一个单词的首末字母相同时，它就是一个自环。所以图至多有26个点，统计出现过的点（首尾字母）。 建图完毕后，先判断是否存在欧拉路（这里包括欧拉通路和欧拉回路），再 DFS 寻找字典序最小的欧拉路。 1）以单词为边，单词的首字母和末字母为点连边，统计出现过的点（字母）； 2）存下对应的无向图，随便跑一下并查集，检验联通块的个数是不是1； 3）建图的时候顺便统计点的度数，然后判断是哪种情况，之后递归构造答案就行了。