题干：

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms: 

dog.gopher

gopher.rat

rat.tiger

aloha.aloha

arachnid.dog


A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example, 

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

Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.

Input

The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.

Output

For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.

Sample Input

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

Sample Output

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

题目大意：

  给n个字符串，让你串成一个串，要求输出顺序，如果多解要求字典序最小

解题报告：

   不用并查集判连通，用dfs判连通就行了。注意路径记录的时候要先dfs再回溯记录，因为可能有这种情况。

所以你需要再倒回来路径的时候记录路径，因为首先欧拉通路他只有一个终点（再也走不动的地方），你最后走不动了回溯的时候着一定是倒着回溯的，最后倒着输出就行了。

再就是注意搜索的起点：

（1）如果发现所有节点的出度与入度都相等，那么有向图中存在欧拉回路，当然也一定存在欧拉通路了。这时以任一节点开始深搜一条路径即可。（因为字典序要求最小我们就从出现的字符集中最小的那个字母开始搜）
（2）如果发现存在 out[i] - in[i] == 1 的节点，那么欧拉通路是以out[i] - in[i] == 1的那个 i 为始点的，以 in[i] - out[i] == 1 的那个 i 为终点。这时我们要以这个out[i] - in[i] == 1 的节点为起点开始深搜。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<string,int> PSI;
const int MAX = 1000 + 5;
string s[MAX];
int n;
string ans[MAX];
int len[MAX],in[MAX],out[MAX],tot; 
bool vis[MAX];
vector<PSI> vv[129];
void dfs(char st) {
	int up = vv[st].size();
	for(int i = 0; i<up; i++) {
		PSI cur = vv[st][i];
		if(vis[cur.S]) continue;
		vis[cur.S] = 1;		
		dfs(cur.F[len[cur.S]-1]);		
		ans[++tot] = cur.F;
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--) {
		tot=0;
		scanf("%d",&n);
		for(int i = 1; i<=127; i++) in[i]=out[i]=0,vv[i].clear();
		for(int i = 1; i<=n; i++) {
			vis[i] = 0;
			cin>>s[i];len[i] = s[i].length();
		}
		char minn = 'z';
		for(int i = 1; i<=n; i++) {			
			char st = s[i][0];
			char ed = s[i][len[i]-1];
			vv[st].pb(pm(s[i],i));
			in[ed]++;
			out[st]++;
			minn = min(minn,ed);minn = min(minn,st);
		}
		int flag = 1,ru=0,chu=0;
		for(int i = 'a'; i<='z'; i++) {
			sort(vv[i].begin(),vv[i].end());
			if(!in[i] && !out[i]) continue;
			if(in[i] == out[i]) continue;
			else if(in[i] - out[i] == 1) ru++;
			else if(out[i] - in[i] == 1) chu++,minn=i;
			else {flag = 0;break;}
		}
		if(flag == 0 || ru>1 || chu>1 || ru!=chu) puts("***");
		else {
			dfs(minn);
			if(tot != n) puts("***");
			else {
				for(int i = n; i>=1; i--) {
					if(i != n) printf(".");
					cout << ans[i];
				}
				puts("");
			}
		}
	} 
	return 0 ;
}