#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> sz, ord, pos, vil;
int mn, mx;
int get_sz(int no, int rt) {
sz[no] = 1;
for(auto i: g[no]) {
if(i == rt) continue;
sz[no] += get_sz(i, no);
}
return sz[no];
}
int get_cent(int no, int rt, int siz) {
for(auto i: g[no]) {
if(i == rt) continue;
if(sz[i] > siz/2) return get_cent(i, no, siz);
}
return no;
}
void dfs(int no, int rt, int dis) {
ord.push_back(no);
mx += 2*dis;
for(auto i: g[no]) {
if(i == rt) continue;
dfs(i, no, dis+1);
}
}
void dfs_mn(int no, int rt) {
for(auto i: g[no]) {
if(i == rt) continue;
dfs_mn(i, no);
}
if(rt == -1 && vil[no] == no) {
swap(vil[no], vil[g[no][0]]);
mn += 2;
} else if(vil[no] == no) {
swap(vil[no], vil[rt]);
mn += 2;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
sz.assign(n+2, 0);
g.assign(n+2, vector<int>());
pos.assign(n+2, 0);
vil.assign(n+2, 0);
for(int i=1; i<=n; i++) vil[i] = i;
for(int i=1; i<n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
ord.push_back(-1);
get_sz(1, -1);
int cent = get_cent(1, -1, n);
dfs(cent, -1, 0);
dfs_mn(1, -1);
for(int i=1; i<=n; i++) {
if(i+n/2 <= n) pos[ord[i]] = ord[i+n/2];
else pos[ord[i]] = ord[i+n/2-n];
}
cout << mn << " " << mx << "\n";
for(int i=1; i<=n; i++) {
cout << vil[i] << " ";
}
cout << "\n";
for(int i=1; i<=n; i++) {
cout << pos[i] << " ";
}
}
