//PKU 2337 #include <cstdio> #include <string> #include <vector> #include <stack> #include <algorithm> using namespace std; const int MAX = 1100; char str[MAX][25]; int n, in[MAX], out[MAX]; vector<string> words[30]; int vis[30]; int f[30], ss, is, os, ps; int seq[MAX], step; void find_euler(int pos) { int i,j; while(out[pos]) { for(; vis[pos] < words[pos].size() ;) { string snext = words[pos][ vis[pos] ]; j = snext[snext.length() -1] -’a’; out[pos] --; vis[pos] ++; find_euler(j); } } seq[step ++] = pos; } void union_f(int s,int e) { int ts = s, te = e; while(s != -1 && f[s] != s) { s = f[s]; } if(s == -1) { f[ts] = s = ts; } while(e != -1 && f[e] != e) { int t = e; e = f[e]; f[t] = s; } if(e >= 0) { f[e] = s; } } int main() { int t,i,j; scanf("%d", &t); while(t --) { scanf("%d", &n); getchar(); for(i=0;i<30;i++) words[i].clear(); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(f,-1,sizeof(f)); ss = is = os = ps = 0; for(i=0;i<n;i++) { gets(str[i]); int len = strlen(str[i]); int chs = str[i][0] -’a’; int che = str[i][len-1] -’a’; words[chs].push_back(string(str[i])); in[che] ++; out[chs] ++; union_f(chs, che); } bool flag = true; for(i=0;i<30;i++) { if(f[i] == i) ss ++; if(in[i] == out[i] +1) os ++; else if(in[i] +1 == out[i]) is ++; else if(in[i] != out[i]) flag = false; } if(ss > 1) flag = false; if( !(os==0 && is==0) && !(os==1 && is==1) ) flag = false; if(!flag) { puts("***"); } else { int spos; if(os == 1 && is == 1) { for(i=0;i<30;i++) { if(in[i] +1 == out[i]) { spos = i; break; } } } else { for(i=0;i<30;i++) { if(f[i] != -1) { spos = i; break; } } } for(i=0;i<30;i++) sort(words[i].begin(), words[i].end()); step = 0; memset(vis, 0, sizeof(vis)); find_euler(spos); //memset(vis, 0, sizeof(vis)); for(i=step-1;i>0;i--) { spos = seq[i]; string snext; for(j=0;j<words[spos].size();j++) { snext = words[spos][j]; if(seq[i-1] == snext[snext.length() -1] -’a’) { words[spos].erase(words[spos].begin() +j); break; } } printf("%s", snext.c_str()); if(i>1) putchar(’.’); } puts(""); } } }