题目描述

请注意本题目数据范围与洛谷原题不同。

洛谷上的题目数据十分的水。本数据故意构造了重边和自环。

如果单词 $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 10000$），代表单词数量。

接下来共有 $n$ 行，每行是一个由 $1$ 到 $20$ 个小写字母组成的单词。

输出格式

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

样例 #1

6
aloha
arachnid
dog
gopher
rat
tiger

aloha.arachnid.dog.gopher.rat.tiger

提示

• 对于 $100\%$ 的数据，有 $n \leq 10000$。