P1127 Word Chain

If the last letter of word $X$ is the same as the first letter of word $Y$, then $X$ and $Y$ can be concatenated as $X.Y$. Note: there is an English period `.` between $X$ and $Y$. For example, for the words `dog` and `gopher`, `dog` and `gopher` can be concatenated as `dog.gopher`. More examples: - `dog.gopher` - `gopher.rat` - `rat.tiger` - `aloha.aloha` - `arachnid.dog` A concatenated word can be connected with other words to form a longer word chain, for example: `aloha.arachnid.dog.gopher.rat.tiger` Note that the letters on both sides of `.` must be the same. Now you are given some words. Please find the lexicographically smallest word chain such that each word appears in the chain exactly once. Note that if the same word appears $k$ times, you must output it $k$ times.

The first line contains a positive integer $n$ ($1 \le n \le 1000$), representing the number of words. The next $n$ lines each contain a word consisting of $1$ to $20$ lowercase letters.

Output a single line: the lexicographically smallest word chain that uses every given word exactly once. If such a chain does not exist, output exactly three asterisks `***`.

- For $40\%$ of the testdata, $n \le 10$. - For $100\%$ of the testdata, $n \le 1000$. Translated by ChatGPT 5