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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>


using namespace std;


void backtrack(long long mask, int n, vector <vector<int>> &g, int nextLabel, vector <int> &label, vector <int> &seq, vector <int> &seqBest) {
    if (!seqBest.empty() && seq > seqBest) {
        return ;
    }

    if (__builtin_popcountll(mask) <= 2) {
        seqBest = seq;
        return ;
    }

    vector <int> labeled;

    auto addToSeq = [&](int v) {
        if (label[v] == -1) {
            labeled.push_back(v);
            label[v] = nextLabel++;
        }

        seq.push_back(label[v]);
    };

    auto revert = [&]() {
        for (int v : labeled) {
            label[v] = -1;
            nextLabel--;
        }

        labeled.clear();
    };

    long long maskLeaf = 0;
    for (int i = 0; i < n; i++) if (mask & (1LL << i)) {
        bool leaf = true;
        int neigh = -1;

        for (int j : g[i]) if (mask & (1LL << j)) {
            if (neigh == -1) {
                neigh = j;
            } else {
                leaf = false;
                break;
            }
        }

        if (leaf) {
            maskLeaf ^= 1LL << i;

            if (label[i] != -1) {
                addToSeq(neigh);
                backtrack(mask ^ (1LL << i), n, g, nextLabel, label, seq, seqBest);

                revert();
                seq.pop_back();

                return ;
            }
        }
    }

    for (int i = 0; i < n; i++) if (maskLeaf & (1LL << i)) {
        int neigh = -1;
        for (int j : g[i]) if (mask & (1LL << j)) {
            neigh = j;
        }

        long long maskNext = mask, origLen = seq.size();
        for (int j : g[neigh]) if (maskLeaf & (1LL << j)) {
            maskNext ^= 1LL << j;
            addToSeq(neigh);
        }

        backtrack(maskNext, n, g, nextLabel, label, seq, seqBest);

        revert();
        seq.resize(origLen);
    }
}

vector <int> solve(int n, vector <vector<int>> &g) {
    vector <int> label(n, -1), seq, seqBest;
    backtrack((1LL << n) - 1, n, g, 0, label, seq, seqBest);

    seqBest.resize(n - 2);
    return seqBest;
}

int main() {
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector <vector<int>> g(n);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v; u--; v--;

            g[u].push_back(v);
            g[v].push_back(u);
        }

        auto seq = solve(n, g);
        for (int x : seq) {
            cout << x + 1 << ' ';
        }

        cout << '\n';
    }

    return 0;
}