#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> edges;
edges.reserve(max(0, n - 1));
vector<vector<int>> incident(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
int id = (int)edges.size();
edges.push_back({u, v});
incident[u].push_back(id);
incident[v].push_back(id);
}
auto dist = [&](int a, int b) {
int d = abs(a - b);
if (d > n - d) d = n - d;
return d;
};
vector<int> perm(n), pos(n + 1);
iota(perm.begin(), perm.end(), 1);
for (int i = 0; i < n; ++i) {
pos[i + 1] = i;
}
const int max_d = n / 2;
vector<int> cnt(max_d + 1, 0);
int missing = max_d;
auto rebuild = [&]() {
fill(cnt.begin(), cnt.end(), 0);
missing = max_d;
for (auto [u, v] : edges) {
int d = dist(pos[u], pos[v]);
if (cnt[d]++ == 0) --missing;
}
};
auto touch = [&](int x, int sign, int skip) {
for (int idx : incident[x]) {
auto [u, v] = edges[idx];
int y = u ^ v ^ x;
if (y == skip) continue;
int d = dist(pos[x], pos[y]);
if (sign == 1) {
if (cnt[d] == 0) --missing;
++cnt[d];
} else {
if (cnt[d] == 1) ++missing;
--cnt[d];
}
}
};
auto do_swap = [&](int i, int j) {
int a = perm[i];
int b = perm[j];
touch(a, -1, -1);
touch(b, -1, a);
swap(perm[i], perm[j]);
swap(pos[a], pos[b]);
touch(a, +1, -1);
touch(b, +1, a);
};
auto randomize = [&](mt19937 &rng) {
shuffle(perm.begin(), perm.end(), rng);
for (int i = 0; i < n; ++i) pos[perm[i]] = i;
rebuild();
};
rebuild();
vector<int> best_perm = perm;
int best_missing = missing;
mt19937 rng(0xBADC0DEu + static_cast<uint32_t>(n));
uniform_int_distribution<int> idx_dist(0, n - 1);
uniform_int_distribution<int> idx2_dist(0, n - 2);
uniform_int_distribution<int> jump_dist(0, 9999);
if (missing > 0) {
for (int restart = 0; restart < 25 && missing > 0; ++restart) {
if (restart == 0) {
randomize(rng);
} else {
randomize(rng);
}
int stuck = 0;
for (int it = 0; it < 70000 && missing > 0; ++it) {
int before = missing;
int i = idx_dist(rng);
int j = idx2_dist(rng);
if (j >= i) ++j;
do_swap(i, j);
bool accept = false;
if (missing < before) {
accept = true;
} else if (missing == before) {
accept = jump_dist(rng) < 2200; // 22%
} else {
accept = jump_dist(rng) < 30; // 0.3%
}
if (!accept) {
do_swap(i, j); // revert
++stuck;
} else {
stuck = 0;
if (missing < best_missing) {
best_missing = missing;
best_perm = perm;
}
if (missing == 0) {
break;
}
}
if (stuck > 20000) {
break;
}
}
}
}
if (best_missing < missing) {
perm = best_perm;
for (int i = 0; i < n; ++i) {
pos[perm[i]] = i;
}
}
for (int shift = 0; shift < n; ++shift) {
for (int i = 0; i < n; ++i) {
if (i) cout << ' ';
cout << perm[(i + shift) % n];
}
cout << '\n';
}
return 0;
}
