#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int MAX_N = 1e5 + 10;
int timer;
long long ans1, ans2;
int sz[MAX_N], depth[MAX_N], parent[MAX_N][20];
vector <int> graph[MAX_N];
int pos[MAX_N], nhouse1[MAX_N], nhouse2[MAX_N];
void dfs1(const int &u, const int &p) {
for(auto v : graph[u]) {
if(v != p) {
dfs1(v, u);
}
}
if(nhouse1[u] == u) {
ans1 += 2;
if(p != -1) {
swap(nhouse1[u], nhouse1[p]);
}
else {
swap(nhouse1[1], nhouse1[graph[1][0]]);
}
}
}
int get_size(const int &u, const int &p) {
sz[u] = 1;
for(auto v : graph[u]) {
if(v != p) {
sz[u] += get_size(v, u);
}
}
return sz[u];
}
int get_centroid(const int &u, const int &p, const int &n) {
for(auto v : graph[u]) {
if(v != p and sz[v] > n / 2) {
return get_centroid(v, u, n);
}
}
return u;
}
void dfs2(const int &u, const int &p) {
pos[++timer] = u;
for(int i = 1; i < 20; i++) {
parent[u][i] = parent[parent[u][i - 1]][i - 1];
}
for(auto v : graph[u]) {
if(v == p) {
continue;
}
depth[v] = depth[u] + 1;
parent[v][0] = u;
dfs2(v, u);
}
}
int find_lca(const int &a, const int &b) {
int u = a, v = b;
if(depth[u] < depth[v]) {
swap(u, v);
}
for(int i = 19; i >= 0; i--) {
if(depth[parent[u][i]] >= depth[v]) {
u = parent[u][i];
}
}
for(int i = 19; i >= 0; i--) {
if(parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
return (u == v ? u : parent[u][0]);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N;
cin >> N;
for(int i = 1; i <= N; i++) {
nhouse1[i] = i;
}
for(int i = 1; i <= N - 1; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs1(1, -1);
dfs2(get_centroid(1, -1, get_size(1, -1)), -1);
for(int i = 1; i <= N; i++) {
nhouse2[pos[i]] = pos[(i + N / 2 - 1) % N + 1];
}
for(int i = 1; i <= N; i++) {
ans2 += depth[i] + depth[nhouse2[i]] - 2 * depth[find_lca(i, nhouse2[i])];
}
cout << ans1 << ' ' << ans2 << '\n';
for(int i = 1; i <= N; i++) {
cout << nhouse1[i] << ' ';
}
cout << '\n';
for(int i = 1; i <= N; i++) {
cout << nhouse2[i] << ' ';
}
return 0;
}
