#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
const long long MAX = 1'000'000'000'000'000'000;
int n;
vector<int> ad[N];
namespace findMin {
long long f[N][2];
vector<tuple<int, int, int>> trace[N][2];
void dfs0(int u, int p = -1) {
f[u][1] = 0;
vector<int> best;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs0(v, u);
best.push_back(v);
}
if (best.size()) {
sort(best.begin(), best.end(), [&](const auto& a, const auto& b) {
return f[a][1] - f[a][0] > f[b][1] - f[b][0];
});
{ //f[u][1]
vector<int> vt = best;
auto& ret = f[u][1];
auto& tr = trace[u][1];
while (vt.size() > 1) {
long long value = min(MAX, f[vt.back()][1] + f[vt.end()[-2]][1] + 4);
if (value <= min(MAX, f[vt.back()][0] + f[vt.end()[-2]][0])) {
ret = min(MAX, ret + value);
tr.emplace_back(0, vt.back(), vt.end()[-2]);
vt.pop_back();
vt.pop_back();
} else break;
}
for (const auto& x : vt) {
ret = min(MAX, ret + f[x][0]);
tr.emplace_back(1, x, 0);
}
}
{ //f[u][0]
vector<int> vt = best;
auto& ret = f[u][0];
auto& tr = trace[u][0];
ret = f[vt.back()][1] + 2;
tr.emplace_back(2, vt.back(), 1);
vt.pop_back();
for (const auto& x : vt) {
if (f[x][1] + 2 <= f[x][0]) {
ret = min(MAX, ret + f[x][1] + 2);
tr.emplace_back(2, x, 1);
} else {
ret = min(MAX, ret + f[x][0]);
tr.emplace_back(2, x, 0);
}
}
}
if (f[u][0] > f[u][1] + 2) {
f[u][0] = min(MAX, f[u][1] + 2);
trace[u][0] = {make_tuple(3, best.back(), 0)};
}
}
if (f[u][1] >= MAX || f[u][1] < 0) f[u][1] = 2 * MAX;
if (f[u][0] >= MAX || f[u][0] < 0) f[u][0] = MAX;
}
int vt[N];
void dfs1(int u, int st) {
for (const auto& [type, a, b] : trace[u][st]) {
if (!type) {
dfs1(a, 1); dfs1(b, 1);
swap(vt[a], vt[b]);
} else if (type == 1) {
dfs1(a, 0);
} else if (type == 2) {
dfs1(a, b);
if (b) swap(vt[u], vt[a]);
} else {
dfs1(u, 1);
swap(vt[u], vt[a]);
}
}
}
int length;
vector<int> answer;
void solve() {
memset(f, 14, sizeof f);
dfs0(1);
iota(vt + 1, vt + n + 1, 1);
dfs1(1, 0);
length = f[1][0];
answer = vector<int>(vt + 1, vt + n + 1);
}
}
namespace findMax {
long long length;
int sz[N], st[N], it;
void dfs0(int u, int p = -1) {
st[u] = ++it;
sz[u] = 1;
for (const auto& v : ad[u]) {
if (v == p) continue;
dfs0(v, u);
sz[u] += sz[v];
length += 2 * min(sz[v], n - sz[v]);
}
}
vector<int> answer;
void solve() {
dfs0(1);
vector<pair<int, int>> vt;
for (int i = 1; i <= n; ++i) vt.push_back({i, i});
sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { return st[a.first] < st[b.first]; });
for (int i = 1; i <= n; ++i) swap(vt[i - 1].first, vt[(i + n / 2) % n].first);
answer.resize(n);
for (const auto& x : vt) answer[x.second - 1] = x.first;
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
ad[u].push_back(v);
ad[v].push_back(u);
}
findMin::solve();
findMax::solve();
cout << findMin::length << " " << findMax::length << "\n";
for (int i = 0; i < n; ++i) cout << findMin::answer[i] << " \n"[i == n - 1];
for (int i = 0; i < n; ++i) cout << findMax::answer[i] << " \n"[i == n - 1];
}
