#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<vector<int>> adj(N+1);
for(int i=1;i<N;i++){
int u,v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
int answer1 = 0;
vector<int> answer1vec(N+1);
{
// answer 1
int centroid = -1;
{
auto dfs = [&](auto&& self,int x,int p)->int{
int siz = 1;
for(int&i:adj[x])if(i!=p)siz+=self(self,i,x);
if((N-siz)<=N/2){
centroid = x;
return -1e10;
}
return siz;
};
dfs(dfs,1,0);
}
vector<int> curr(N+1);
int idx = -1;
auto dfs = [&](auto&& self,int x,int p,int dep)->void{
if(++idx>N/2){
answer1vec[curr[idx-N/2]]=x;
answer1vec[x]=curr[idx-N/2];
} else curr[idx]=x;
answer1+=2ll*dep;
for(int&i:adj[x])if(i!=p)self(self,i,x,dep+1);
};
dfs(dfs,centroid,0,0);
if(N&1){
answer1vec[centroid]=answer1vec[curr[1]];
answer1vec[curr[1]]=centroid;
} else {
answer1vec[curr[N/2]]=centroid;
answer1vec[centroid]=curr[N/2];
}
}
int answer2 = 0;
vector<int> answer2vec(N+1);
{
iota(answer2vec.begin(),answer2vec.end(),0);
auto addInChain = [&](int x,int y){
answer2vec[y]=answer2vec[x];
return answer2vec[x]=y;
};
auto dfs = [&](auto&& self,int x,int p)->bool{
vector<int> childrenNeeding;
for(int&i:adj[x])if(i!=p){
if(self(self,i,x))childrenNeeding.emplace_back(i);
}
if(childrenNeeding.empty())return true;
int last = x;
for(int&i:childrenNeeding)last=addInChain(last,i);
answer2+=(int)childrenNeeding.size()*2ll;
return false;
};
if(dfs(dfs,1,0)){
addInChain(adj[1][0],1);
answer2+=2;
}
}
cout << answer2 << ' ' << answer1 << '\n';
for(int i=1;i<=N;i++)cout<<answer2vec[i]<<' ';
cout << '\n';
for(int i=1;i<=N;i++)cout<<answer1vec[i]<<' ';
cout << '\n';
}
