|
|
#include <iostream>
|
|
|
#include <cstdio>
|
|
|
#include <cmath>
|
|
|
#include <cstring>
|
|
|
#include <string>
|
|
|
#include <algorithm>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1200, M = N * N;
|
|
|
int n;
|
|
|
int din[N], dout[N];
|
|
|
string s[N];
|
|
|
|
|
|
int res[N], rl;
|
|
|
|
|
|
// 链式前向星
|
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
|
void add(int a, int b, int c = 0) {
|
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// 记录边的dfs,要注意记录边和记录点的差别
|
|
|
void dfs(int u) {
|
|
|
for (int i = h[u]; ~i; i = h[u]) {
|
|
|
h[u] = ne[i];
|
|
|
dfs(e[i]);
|
|
|
res[++rl] = w[i];
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int getStart() {
|
|
|
int st = 0, a = 0, b = 0, c = 0;
|
|
|
for (int i = 0; i < 26; i++) { // 枚举每个有效节点,每道题的具体实现可能有差异
|
|
|
if (dout[i] != din[i]) a++; // 出度与入度不一致的数量
|
|
|
if (dout[i] == din[i] + 1) b++, st = i; // 起点数量，记录起点
|
|
|
if (dout[i] == din[i] - 1) c++; // 终点数量
|
|
|
}
|
|
|
if (a && (b != 1 || c != 1)) return -1; // 如果有不一致的，并且不是1个，则没有欧拉路径
|
|
|
// 如果是一个环，也是存在欧拉路径的，但所有点的入度和出度一致，st不会被改写，需要再手找出起点。
|
|
|
while (!dout[st]) st++;
|
|
|
return st;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("POJ2337.in", "r", stdin);
|
|
|
#endif
|
|
|
int T;
|
|
|
scanf("%d", &T);
|
|
|
while (T--) {
|
|
|
memset(din, 0, sizeof din);
|
|
|
memset(dout, 0, sizeof dout);
|
|
|
memset(h, -1, sizeof h);
|
|
|
idx = 0;
|
|
|
|
|
|
scanf("%d", &n);
|
|
|
|
|
|
for (int i = 1; i <= n; i++) cin >> s[i]; // 第几个字符串
|
|
|
sort(s + 1, s + n + 1); // 字典序，排序由小到大
|
|
|
|
|
|
for (int i = n; i; i--) { // 倒序枚举，就是由大到小
|
|
|
int a = s[i][0] - 'a', b = s[i][s[i].size() - 1] - 'a';
|
|
|
din[b]++, dout[a]++;
|
|
|
add(a, b, i);
|
|
|
}
|
|
|
|
|
|
int start = getStart();
|
|
|
|
|
|
if (start == -1) {
|
|
|
printf("***\n");
|
|
|
continue;
|
|
|
}
|
|
|
|
|
|
// 从start开始搜索，找出欧拉路径，是有向图的欧拉路径，不是欧拉回路
|
|
|
rl = 0; // 清空路径数组游标，准备开始填充路径
|
|
|
dfs(start);
|
|
|
|
|
|
if (rl != n) { // 无法遍历到所有的点
|
|
|
printf("***\n");
|
|
|
continue;
|
|
|
}
|
|
|
|
|
|
// 控制格式输出
|
|
|
for (int i = n; i > 1; i--) {
|
|
|
cout << s[res[i]];
|
|
|
printf(".");
|
|
|
}
|
|
|
cout << s[res[1]] << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
} |
