#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
cin >> n;
vector<vector<int>> tree(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u, --v;
tree[u].push_back(v);
tree[v].push_back(u);
}
vector<int> order;
vector<int> tin(n);
vector<array<int, 2>> dp(n, array<int, 2>{});
vector<int> siz(n);
vector<int> upto(n);
vector<int> vis(n);
auto dfs = [&](auto&& self, int v) -> void {
tin[v] = order.size();
order.push_back(v);
vis[v] = 1;
vector<int> del;
vector<int> kids;
siz[v] = 1;
for (int nxt : tree[v]) {
if (vis[nxt]) {
continue;
}
self(self, nxt);
kids.push_back(nxt);
del.push_back(dp[nxt][1] - dp[nxt][0]);
dp[v][1] += max(dp[nxt][0], dp[nxt][1]);
dp[v][0] += dp[nxt][0];
siz[v] += siz[nxt];
}
tree[v] = kids;
if (!del.empty()) {
sort(tree[v].begin(), tree[v].end(), [&](auto lhs, auto rhs) -> bool {
return dp[lhs][1] - dp[lhs][0] > dp[rhs][1] - dp[rhs][0];
});
sort(del.begin(), del.end(), greater<>());
int ind = 0;
while (ind < del.size() && del[ind] >= 0) {
dp[v][0] += del[ind];
++ind;
}
if (ind == 0) {
dp[v][0] += del[ind];
++ind;
}
upto[v] = ind;
dp[v][0] += 2;
} else {
dp[v][0] = -1;
}
};
dfs(dfs, 0);
vector<int> good(n);
auto dfs2 = [&](auto&& self, int v, int want = 0) -> void {
if (want == 0) {
good[v] = 1;
}
if (want == 0) {
for (int i = 0; i < upto[v]; i++) {
int nxt = tree[v][i];
self(self, nxt, 1);
}
for (int i = upto[v]; i < tree[v].size(); i++) {
int nxt = tree[v][i];
self(self, nxt, 0);
}
} else {
for (int i = 0; i < tree[v].size(); i++) {
int nxt = tree[v][i];
if (dp[nxt][0] > dp[nxt][1]) {
self(self, nxt, 0);
} else {
self(self, nxt, 1);
}
}
}
};
fill(vis.begin(), vis.end(), 0);
dfs2(dfs2, 0);
vector<int> ans(n);
for (int i = 0; i < n; i++) {
if (!good[i] || vis[i]) {
continue;
}
vector<int> comp;
queue<int> q;
vis[i] = 1;
q.push(i);
while (!q.empty()) {
int v = q.front();
q.pop();
comp.push_back(v);
for (int nxt : tree[v]) {
if (!good[nxt]) {
vis[nxt] = 1;
q.push(nxt);
}
}
}
assert(comp.size() >= 2);
sort(comp.begin(), comp.end(), [&](auto lhs, auto rhs) -> bool {
return tin[lhs] < tin[rhs];
});
int siz = comp.size();
for (int i = 0; i < siz; i++) {
ans[comp[i]] = comp[(i + 1) % siz];
}
}
i64 big = 0;
for (int i = 0; i < n; i++) {
big += min(n - siz[i], siz[i]);
}
big *= 2;
cout << 2 * n - dp[0][0] << ' ' << big << '\n';
for (int i = 0; i < n; i++) {
cout << ans[i] + 1 << ' ';
}
cout << '\n';
for (int i = 0; i < n; i++) {
cout << 1 << ' ';
}
cout << '\n';
return 0;
}
