#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define int ll
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#ifndef LOCAL
#define endl "\n"
#endif
mt19937 rnd(11);
const int LOG_N = 20;
vector<vector<int>> graph;
vector<int> tin, tout, high, sz;
vector<int> binup[LOG_N];
int Tm = 0;
void calc(int v, int h, int prev = 0) {
sz[v] = 1;
high[v] = h++;
binup[0][v] = prev;
tin[v] = Tm++;
for (auto &u : graph[v]) {
if (u != prev) {
calc(u, h, v);
sz[v] += sz[u];
}
}
tout[v] = Tm;
}
int find_center(int v, int prev = -1) {
for (auto &u : graph[v]) {
if (u != prev && sz[u] * 2 >= sz[0]) {
return find_center(u, v);
}
}
return v;
}
bool inside(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca(int a, int b) {
if (inside(a, b)) {
return a;
}
for (int l = LOG_N - 1; l >= 0; --l) {
if (!inside(binup[l][a], b)) {
a = binup[l][a];
}
}
return binup[0][a];
}
int dist(int a, int b) {
int c = lca(a, b);
return high[a] + high[b] - high[c] * 2;
}
void solve() {
int n;
cin >> n;
tin.resize(n);
tout.resize(n);
high.resize(n);
sz.resize(n);
binup[0].resize(n);
graph.resize(n);
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
graph[a].pb(b);
graph[b].pb(a);
}
calc(0, 0);
for (int l = 1; l < LOG_N; ++l) {
binup[l].resize(n);
for (int i = 0; i < n; ++i) {
binup[l][i] = binup[l - 1][binup[l - 1][i]];
}
}
vector<int> ans1(n), ans2(n);
{
int center = find_center(0);
vector<vector<int>> vertex;
auto dfs = [&](int v, int prev, auto &&self) -> void {
vertex.back().pb(v);
for (auto &u : graph[v]) {
if (u != prev) {
self(u, v, self);
}
}
};
for (auto &u : graph[center]) {
vertex.pb({});
dfs(u, center, dfs);
}
if (n % 2 == 0) {
vertex.pb({center});
}
priority_queue<pii> q;
for (int i = 0; i < vertex.size(); ++i) {
q.push(mp(vertex[i].size(), i));
}
int lst;
while (!q.empty()) {
int a = q.top().s;
q.pop();
int b = q.top().s;
q.pop();
lst = vertex[a].back();
ans2[vertex[a].back()] = vertex[b].back();
ans2[vertex[b].back()] = vertex[a].back();
vertex[a].pop_back();
vertex[b].pop_back();
if (!vertex[a].empty()) {
q.push(mp(vertex[a].size(), a));
}
if (!vertex[b].empty()) {
q.push(mp(vertex[b].size(), b));
}
}
if (n % 2 == 1) {
swap(ans2[lst], ans2[center]);
ans2[lst] = center;
}
}
vector<int> p(n);
iota(all(p), 0);
int best = 1e9;
do {
bool ok = true;
int now = 0;
for (int i = 0; i < n; ++i) {
if (p[i] == i) {
ok = false;
break;
}
now += dist(i, p[i]);
}
if (ok && best > now) {
best = now;
ans1 = p;
}
} while (next_permutation(all(p)));
int answer1 = 0, answer2 = 0;
for (int i = 0; i < n; ++i) {
answer1 += dist(i, ans1[i]);
answer2 += dist(i, ans2[i]);
}
cout << answer1 << ' ' << answer2 << endl;
for (auto &x : ans1) {
cout << x+1 << ' ';
}
cout << endl;
for (auto &x : ans2) {
cout << x+1 << ' ';
}
cout << endl;
}
signed main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(0);
#endif
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
