#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
const int MAX_L = __lg(MAX_N) + 1;
int up[MAX_L][MAX_N];
vector<int> G[MAX_N];
int depth[MAX_N], small[MAX_N], large[MAX_N];
vector<int> ord;
void DFS(int u, int p) {
depth[u] = (u == 0 ? 0 : depth[p] + 1);
ord.push_back(u);
up[0][u] = p;
for (int i = 0; i < MAX_L - 1; i++) {
up[i + 1][u] = up[i][up[i][u]];
}
for (int v : G[u]) {
if (v != p) {
DFS(v, u);
}
}
if (small[u] == u) {
swap(small[u], small[u == 0 ? G[u][0] : p]);
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
for (int i = MAX_L - 1; i >= 0; i--) {
if (depth[u] - depth[v] >= (1 << i)) {
u = up[i][u];
}
}
if (u == v) {
return u;
}
for (int i = MAX_L - 1; i >= 0; i--) {
if (up[i][u] != up[i][v]) {
u = up[i][u];
v = up[i][v];
}
}
return up[0][u];
}
int distance(int u, int v) {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N;
cin >> N;
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
G[u].push_back(v);
G[v].push_back(u);
}
iota(small, small + N, 0);
DFS(0, 0);
for (int i = 0; i < N; i++) {
large[ord[i]] = ord[(i + N / 2) % N];
}
int64_t smallest = 0, largest = 0;
for (int i = 0; i < N; i++) {
smallest += distance(i, small[i]);
largest += distance(i, large[i]);
}
cout << smallest << " " << largest << "\n";
for (int i = 0; i < N; i++) {
cout << 1 + small[i] << " \n"[i + 1 == N];
}
for (int i = 0; i < N; i++) {
cout << 1 + large[i] << " \n"[i + 1 == N];
}
}
