#include <bits/stdc++.h>
#define int long long
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
const int MAX_N = 100000+10;
const int INF = 2e18;
int n;
int a, b;
vector<vector<int>> G(MAX_N);
bitset<MAX_N> vis;
int total = 0;
int ma = -INF, mi = INF;
vector<int> ma_ans(MAX_N, -1), mi_ans(MAX_N, -1);
pair<int, int> dfs2(int now, int pre){ // <最遠點距離, 最遠點>
pair<int, int> ret = {0, now};
for (auto x : G[now]){
if (x!=pre && vis[x]==0){
pair<int, int> res = dfs2(x, now);
ret = max(ret, res);
}
}
ret.first++;
return ret;
}
void dfs3(int now, int pre){
// cerr << now << endl;
for (auto x : G[now]){
if (x!=pre){
dfs3(x, now);
}
}
if (mi_ans[now]==-1){
if (pre!=-1){
mi_ans[now] = (mi_ans[pre]==-1 ? pre : mi_ans[pre]);
mi_ans[pre] = now;
}else{
mi_ans[now] = mi_ans[G[now].back()];
mi_ans[G[now].back()] = now;
}
total += 2;
}
return;
}
void solve2(){
// input
cin >> n;
for (int i=0 ; i<n-1 ; i++){
cin >> a >> b;
a--, b--;
G[a].push_back(b);
G[b].push_back(a);
}
// 找到最長的方式
total = 0;
pair<int, int> aa, bb;
for (int i=0 ; i<n/2 ; i++){
for (int j=0 ; j<n ; j++){
if (vis[j]==0){
aa = dfs2(j, -1);
bb = dfs2(aa.second, -1);
vis[aa.second] = 1;
vis[bb.second] = 1;
total += (bb.first-1)*2;
// cerr << "樹直徑：" << aa.second+1 << " & " << bb.second+1 << " 貢獻：" << (bb.first-1)*2 << endl;
ma_ans[aa.second] = bb.second;
ma_ans[bb.second] = aa.second;
break;
}
}
}
if (n%2==1){
for (int i=0 ; i<n ; i++){
if (ma_ans[i]==-1){
ma_ans[i] = ma_ans[aa.second];
ma_ans[aa.second] = i;
}
}
}
ma = total;
// 找到最短的方法
total = 0;
dfs3(0, -1);
mi = total;
// output
cout << mi << " " << ma << "\n";
for (int i=0 ; i<n ; i++){
cout << mi_ans[i]+1 << " ";
}
cout << "\n";
for (int i=0 ; i<n ; i++){
cout << ma_ans[i]+1 << " ";
}
cout << "\n";
return;
}
signed main(){
fastio;
int t = 1;
while (t--){
solve2();
}
return 0;
}
