#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
int mn = 0;
std::vector<int> w(n, -1), o(n, -1);
std::vector<int> siz(n, 1);
std::function<void(int, int)> dfs = [&](int u, int p) {
std::vector<int> a;
int x = -1;
for (int v : adj[u]) {
if (v == p)
continue;
dfs(v, u);
siz[u] += siz[v];
if (w[v] == -1) {
a.push_back(v);
}
x = v;
}
int m = a.size();
if (m % 2 == 1) {
for (int i = 0; i < m - 2; i += 2) {
mn += 4;
w[a[i]] = a[i + 1];
w[a[i + 1]] = a[i];
}
mn += 2;
w[u] = a[m - 1];
w[a[m - 1]] = u;
} else {
for (int i = 0; i < m; i += 2) {
mn += 4;
w[a[i]] = a[i + 1];
w[a[i + 1]] = a[i];
}
if (m >= 2) {
w[u] = a[0];
w[a[0]] = a[1];
w[a[1]] = u;
} else if (p == -1) {
mn += 2;
w[u] = w[x];
w[x] = u;
}
}
};
dfs(0, -1);
std::function<int(int, int)> dfs2 = [&](int u, int p) {
for (int v : adj[u]) {
if (v != p && siz[v] > n / 2) {
return dfs2(v, u);
}
}
return u;
};
int u = dfs2(0, -1);
i64 mx = 0;
std::vector<std::vector<int>> a(n);
std::priority_queue<std::pair<int, int>> q;
for (int v : adj[u]) {
std::vector<int> b;
std::function<void(int, int, int)> dfs = [&](int u, int p, int dep) {
b.push_back(u);
mx += dep;
for (int v : adj[u]) {
if (v != p) {
dfs(v, u, dep + 1);
}
}
};
dfs(v, u, 1);
a[v] = b;
q.emplace(b.size(), v);
}
while (q.size() > 1) {
auto [si, i] = q.top();
q.pop();
auto [sj, j] = q.top();
q.pop();
o[a[i].back()] = a[j].back();
o[a[j].back()] = a[i].back();
a[i].pop_back();
a[j].pop_back();
if (si > 1) {
q.emplace(si - 1, i);
}
if (sj > 1) {
q.emplace(sj - 1, j);
}
}
if (q.empty()) {
int v = adj[u][0];
o[u] = o[v];
o[v] = u;
} else {
auto [si, i] = q.top();
assert(a[i].size() == 1);
o[u] = a[i][0];
o[a[i][0]] = u;
}
std::cout << mn << " " << 2 * mx << "\n";
for (int i = 0; i < n; i++) {
std::cout << w[i] + 1 << " \n"[i == n - 1];
}
for (int i = 0; i < n; i++) {
std::cout << o[i] + 1 << " \n"[i == n - 1];
}
return 0;
}
