#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f[100005],nd,mi,mis[100005],mas[100005];
vector<int>v[100005];
vector<int>dq;
int dfs1(int x,int y){
int temp=0;
f[x]=0;
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=y) f[x]+=dfs1(v[x][i],x)+1;
}
return f[x];
}
int dfs2(int x,int y){
for(int i=0;i<v[x].size();i++){
if(f[v[x][i]]>a/2+a%2 and v[x][i]!=y){
return dfs2(v[x][i],x);
}
}
return x;
}
int dfs3(int x,int y,int z){
int ret=0,temp=-1,car=0;
if(x==nd){
for(int i=0;i<v[x].size();i++){
if(f[v[x][i]]>temp){
temp=f[v[x][i]];
car=v[x][i];
}
}
ret+=2*z+dfs3(car,x,2);
}
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=y and v[x][i]!=car){
ret+=z*2+dfs3(v[x][i],x,z+1);
}
}
dq.push_back(x);
return ret;
}
bool dfs4(int x,int y){
int temp=0,fi=0,pi=0;
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=y){
if(dfs4(v[x][i],x)){
temp++;
if(fi==0) fi=v[x][i],pi=v[x][i];
else{
mis[pi]=v[x][i];
pi=v[x][i];
}
}
}
}
if(temp==0) return 1;
else{
mis[pi]=x;
mis[x]=fi;
mi+=temp*2;
return 0;
}
}
int main(){
cin>>a;
for(int i=0;i<a-1;i++){
cin>>b>>c;
v[b].push_back(c);
v[c].push_back(b);
}
dfs1(1,0);
nd=dfs2(1,0);
// cout<<nd<<"\n";
if(dfs4(nd,0)==1){
mis[nd]=mis[v[nd][0]];
mis[v[nd][0]]=nd;
cout<<mi+2<<' ';
}
else cout<<mi<<' ';
cout<<dfs3(nd,0,1)<<"\n";
for(int i=1;i<=a;i++){
cout<<mis[i]<<' ';
}
for(int i=0;i<a;i++){
mas[dq[i]]=dq[(i+a/2)%a];
}
cout<<"\n";
for(int i=1;i<=a;i++){
cout<<mas[i]<<" ";
}
}
