Lexicographically Smallest Word Chain

Given a list of words, you need to arrange them into a chain such that each word appears exactly as many times as it is given. Two words \(X\) and \(Y\) can be connected as \(X.Y\) if and only if the last letter of \(X\) is the same as the first letter of \(Y\). For example, the words dog and gopher can form dog.gopher because the last letter of dog (i.e. \(g\)) is the same as the first letter of gopher (i.e. \(g\)).

You may further connect words to form a longer chain (e.g. aloha.arachnid.dog.gopher.rat.tiger in which every adjoining pair complies with the rule). Your task is to find the lexicographically smallest valid chain that uses every word from the input exactly once. Note that if a word appears multiple times in the input, then it must appear that many times in the chain.

inputFormat

The first line contains an integer \(N\) (with \(N\) small enough, e.g. \(N \le 10\)) representing the number of words. The next \(N\) lines each contain a word consisting of lowercase English letters.

outputFormat

Output the lexicographically smallest chain formed by connecting the words with a period (i.e. a dot .) in between. For every adjacent pair \(X\) and \(Y\) in the chain, the last letter of \(X\) must equal the first letter of \(Y\).

sample

6
aloha
arachnid
dog
gopher
rat
tiger

aloha.arachnid.dog.gopher.rat.tiger