1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

// https://cp-algorithms.com/graph/pruefer_code.html
vector<vector<int>> adj;
vector<int> parent;

void dfs(int v) {
    for (int u : adj[v]) {
        if (u != parent[v]) {
            parent[u] = v;
            dfs(u);
        }
    }
}

vector<int> pruefer_code() {
    int n = adj.size();
    parent.resize(n);
    parent[n-1] = -1;
    dfs(n-1);

    int ptr = -1;
    vector<int> degree(n);
    for (int i = 0; i < n; i++) {
        degree[i] = adj[i].size();
        if (degree[i] == 1 && ptr == -1)
            ptr = i;
    }

    vector<int> code(n - 2);
    int leaf = ptr;
    for (int i = 0; i < n - 2; i++) {
        int next = parent[leaf];
        code[i] = next;
        if (--degree[next] == 1 && next < ptr) {
            leaf = next;
        } else {
            ptr++;
            while (degree[ptr] != 1)
                ptr++;
            leaf = ptr;
        }
    }

    return code;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<pair<int, int>> pol;
        vector<int> p(n);
        for (int i = 1; i < n; i++) {
            int a, b; cin >> a >> b;
            pol.push_back({a - 1, b - 1});
            p[i] = i;
        }

        vector<int> best;
        bool first = true;
        do {
            adj = vector<vector<int>>(n); 
            for (auto e : pol) {
                int a = p[e.first];
                int b = p[e.second];
                adj[a].push_back(b);
                adj[b].push_back(a);
            }

            auto prufer = pruefer_code();
            if (first || prufer < best) {
                best = prufer;
                first = false;
            }

        } while (next_permutation(p.begin(), p.end()));
        
        for (int i = 0; i < n - 2; i++) {
            cout << best[i] + 1 << (i == n - 3 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}