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
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> tree[1001];
vector<int> order;

// source: https://cp-algorithms.com/graph/pruefer_code.html
vector<int> pruefer_code() {
    vector<int> vv = {4, 1, 0, 3, 2};
    set<pair<int, int>> leafs;
    vector<int> degree(n);
    vector<bool> disabled(n, false);
    for (int i = 0; i < n; i++) {
        degree[i] = tree[i].size();
        if (degree[i] == 1)
            leafs.emplace(order[i], i);
    }

    vector<int> code(n - 2);
    for (int i = 0; i < n - 2; i++) {
        auto [o, leaf] = *leafs.begin();
        leafs.erase(leafs.begin());
        disabled[leaf] = true;

        int v;
        for (int u : tree[leaf]) {
            if (!disabled[u])
                v = u;
        }

        code[i] = order[v];
        if (--degree[v] == 1)
            leafs.emplace(order[v], v);
    }

    return code;
}

void solve()
{
    cin >> n;

    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        cin >> a >> b;
        --a; --b;

        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    order.resize(n);
    iota(order.begin(), order.end(), 0);
    vector<int> best;

    do
    {
        auto code = pruefer_code();
        if (best.empty() || code < best) best = code;
    } while (next_permutation(order.begin(), order.end()));

    for (int v : best) cout << v + 1 << ' ';
    cout << '\n';

    order.clear();
    for (int i = 0; i < n; ++i) tree[i].clear();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    for (int i = 0; i < t; ++i) solve();
}