贴个代码，Java版本的：

import java.io.*;
import java.util.*;

public class Main {

//    static class Word {
//        String s;
//        int first;
//        int last;
//
//        public Word(String s) {
//            this.s = s;
//            this.first = s.charAt(0) - 'a';
//            this.last = s.charAt(s.length() - 1) - 'a';
//        }
//    }

    static int n;
    static String[] wordsStr;
    static int[] firstArr;
    static int[] lastArr;
    static int[] path;
    static boolean found;
    final static int N = 30;
    final static int MAXN = (int) (1e3 + 10);

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        wordsStr = new String[MAXN];
        firstArr = new int[MAXN];
        lastArr = new int[MAXN];
        path = new int[MAXN];

        while (t-- > 0) {
            n = Integer.parseInt(br.readLine());
            int[] inDegree = new int[N];
            int[] outDegree = new int[N];
            boolean[] used = new boolean[MAXN];
            found = false;

            for (int i = 0; i < n; i++) {
                String s = br.readLine();
                wordsStr[i] = s;
                firstArr[i] = s.charAt(0) - 'a';
                lastArr[i] = s.charAt(s.length() - 1) - 'a';
                outDegree[firstArr[i]]++;
                inDegree[lastArr[i]]++;
            }
//            Arrays.stream(words, 0, n).forEach(word -> {
//                outDegree[word.first]++;
//                inDegree[word.last]++;
//            });
            Integer[] idx = new Integer[n];
            for (int i = 0; i < n; i++) idx[i] = i;
            Arrays.sort(idx, (a, b) -> wordsStr[a].compareTo(wordsStr[b]));
            String[] tempStr = new String[n];
            int[] tempFirst = new int[n];
            int[] tempLast = new int[n];
            for (int i = 0; i < n; i++) {
                tempStr[i] = wordsStr[idx[i]];
                tempFirst[i] = firstArr[idx[i]];
                tempLast[i] = lastArr[idx[i]];
            }
            System.arraycopy(tempStr, 0, wordsStr, 0, n);
            System.arraycopy(tempFirst, 0, firstArr, 0, n);
            System.arraycopy(tempLast, 0, lastArr, 0, n);
            int start = -1;
            int p = 0, q = 0;
            boolean valid = true;
            for (int i = 0; i < 26; i++) {
                int diff = outDegree[i] - inDegree[i];
                if (diff == 1) {
                    q++;
                    start = i;
                } else if (diff == -1) {
                    p++;
                } else if (diff != 0) {
                    valid = false;
                    break;
                }
            }
            if (!valid || !(p == 0 && q == 0 || p == 1 && q == 1)) {
                bw.write("***\n");
                continue;
            }
            if (p == 0) {
                for (int i = 0; i < 26; i++) {
                    if (outDegree[i] > 0) {
                        start = i;
                        break;
                    }
                }
            }
            dfs(start, 0, used);
            if (found) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    if (i > 0) sb.append('.');
                    sb.append(wordsStr[path[i]]);
                }
                bw.write(sb.toString() + "\n");
            } else {
                bw.write("***\n");
            }
        }
        bw.flush();
    }

    static void dfs(int current, int count, boolean[] used) {
        if (found) {
            return;
        }
        if (count == n) {
            found = true;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i] && firstArr[i] == current) {
                used[i] = true;
                path[count] = i;
                dfs(lastArr[i], count + 1, used);
                if (found) {
                    return;
                }
                used[i] = false;
            }
        }
    }
}