#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, sz[N];
vector<int> g[N];
ll sum_min = 0, sum_max = 0;
vector<int> mnmz, mxmz;
void dfs_min(int u, int p = 0) {
for (auto v : g[u]) {
if (v != p) {
dfs_min(v, u);
if (mnmz[v - 1] == v) {
sum_min += 2;
swap(mnmz[u - 1], mnmz[v - 1]);
}
}
}
}
void solvemin() {
mnmz.resize(n);
iota(mnmz.begin(), mnmz.end(), 1);
return;
dfs_min(1);
if (mnmz[0] == 1) {
sum_min += 2;
swap(mnmz[0], mnmz[g[1][0] - 1]);
}
}
void calc(int u, int p = -1) {
sz[u] = 1;
for (auto v : g[u]) {
if (v != p) {
calc(v, u);
sz[u] += sz[v];
sum_max += 2 * min(n - sz[v], sz[v]);
}
}
}
int centr = -1;
void find_centroid(int u, int p = -1) {
bool good = 1;
for (auto v : g[u]) {
if (v != p) {
find_centroid(v, u);
good &= (2 * sz[v] <= n);
}
}
good &= (2 * (n - sz[u]) <= n);
if (good == 1) centr = u;
}
vector<pair<int, int>> a, b;
void dfs(int u, int orig, int p) {
a.push_back({orig, u});
for (auto v : g[u]) {
if (v != p) {
dfs(v, orig, u);
}
}
}
void solvemax() {
calc(1);
find_centroid(1);
for (auto v : g[centr]) {
dfs(v, v, centr);
}
a.push_back({n + 1, centr});
b = a;
sort(a.begin(), a.begin());
sort(b.rbegin(), b.rend());
int repair = -1;
for (int i = 0; i < n; ++i) {
if (a[i].first == b[i].first) {
repair = a[i].first;
}
}
if (repair != -1) {
vector<int> help;
for (int i = 0; i < n; ++i) {
if (a[i].first != repair && b[i].first != repair) {
help.push_back(i);
}
}
for (int i = 0; i < n; ++i) {
if (a[i].first == b[i].first) {
swap(a[help.back()], a[i]);
help.pop_back();
}
}
}
mxmz.resize(n);
for (int i = 0; i < n; ++i) mxmz[a[i].second - 1] = b[i].second;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
solvemin();
solvemax();
cout << sum_min << " " << sum_max << "\n";
for (auto x : mnmz) cout << x << " ";
cout << "\n";
for (auto x : mxmz) cout << x << " ";
cout << "\n";
return 0;
}
