#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 11;
const int INF = (1LL << 60);
bool vis[MAXN];
vector<int> G[MAXN];
int c_max[MAXN], c_min[MAXN];
template<class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int d[51][51];
int n;
void dijkstra(int s, int ans[]){
fill(ans, ans + n, INF);
fill(vis, vis + n, false);
ans[s] = 0;
min_priority_queue<pair<int, int>> pq; pq.push({0, s});
while(!pq.empty()){
auto [dis, v] = pq.top(); pq.pop();
if(vis[v]) continue; vis[v] = true;
for(auto u : G[v]){
if(ans[u] > ans[v] + 1){
ans[u] = ans[v] + 1;
pq.push({ans[u], u});
}
}
}
}
void naive_dist(){
for(int i = 0; i < n; i++){
dijkstra(i, d[i]);
}
}
int naive_min(){
int p[10]; for(int i = 0; i < n; i++) p[i] = i;
int min_dist = INF;
do{
bool fail = false;
for(int i = 0; i < n; i++) if(p[i] == i) fail = true;
if(fail) continue;
int dist = 0; for(int i = 0; i < n; i++) dist += d[i][p[i]];
min_dist = min(min_dist, dist);
}while(next_permutation(p, p + n));
return min_dist;
}
int naive_max(){
int p[10]; for(int i = 0; i < n; i++) p[i] = i;
int max_dist = -INF;
do{
bool fail = false;
for(int i = 0; i < n; i++) if(p[i] == i) fail = true;
if(fail) continue;
int dist = 0; for(int i = 0; i < n; i++) dist += d[i][p[i]];
max_dist = max(max_dist, dist);
}while(next_permutation(p, p + n));
return max_dist;
}
int counter = 0;
void dfs_min(int v, int pa = -1){
for(auto u : G[v]){
if(u == pa) continue;
dfs_min(u, v);
if(c_min[u] == u) swap(c_min[u], c_min[v]), counter += 2;
}
if(pa == -1 && c_min[v] == v){
for(auto u : G[v]){
if(u == pa) continue;
swap(c_min[u], c_min[v]), counter += 2;
break;
}
}
}
int clever_min(){
for(int i = 0; i < n; i++) c_min[i] = i;
counter = 0;
dfs_min(0);
return counter;
}
int sz[MAXN], p[MAXN];
void dfs_max(int v, int pa = -1){
sz[v] = 1;
for(auto u : G[v]){
if(u == pa) continue;
dfs_max(u, v); p[u] = v; sz[v] += sz[u];
}
}
int centroid(int v, int pa = -1){
for(auto u : G[v]){
if(u == pa) continue;
if(sz[u] >= (n + 1) / 2) return centroid(u, v);
}
return v;
}
vector<int> ST[MAXN];
void dfs_st(int s, int v, int pa = -1){
for(auto u : G[v]){
if(u == pa) continue;
dfs_st(s, u, v);
}
ST[s].push_back(v);
}
int clever_max(){
dfs_max(0);
int c = centroid(0);
dfs_max(c);
int s = 0;
for(int i = 0; i < n; i++){
s += min(sz[i], n - sz[i]) * 2;
}
priority_queue<pair<int, int>> pq;
for(auto v : G[c]){
dfs_st(v, v, c); pq.push({sz[v], v});
}
int prv = -1;
vector<int> ord {c};
while(!pq.empty()){
auto [s, v] = pq.top(); pq.pop();
int u = ST[v][sz[v] - 1]; sz[v]--;
ord.push_back(u);
if(prv != -1 && sz[prv] > 0) pq.push({sz[prv], prv});
prv = v;
}
for(int i = 0; i < n; i++){
c_max[ord[i]] = ord[(i + 1) % n];
}
for(int i = 0; i < n; i++){
if(c_max[i] == i){
swap(c_max[i], c_max[G[i][0]]);
}
}
return s;
}
int32_t main(){
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);
}
int d2_min = clever_min(), d2_max = clever_max();
cout << d2_min << ' ' << d2_max << endl;
for(int i = 0; i < n; i++) cout << c_min[i] + 1 << " \n"[i == n - 1];
for(int i = 0; i < n; i++) cout << c_max[i] + 1 << " \n"[i == n - 1];
}
