#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=3e5+5;
vector<int>v[N];
bool vis[N];
int dst[N];
int ANS[N];
pair<int,int>P;
void dfs(int a, int p){
dst[a]=dst[p]+1;
P=max(P,{dst[a],a});
for(auto b:v[a]){
if(b==p or vis[b])continue;
dfs(b,a);
}
}
signed main(){
int n;
cin>>n;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
v[a].pb(b);
v[b].pb(a);
}
set<int>st;
for(int i=1;i<=n;i++){
st.insert(i);
}
vector<pair<int,int>>vc;
int ans=0;
while(st.size()>1){
int a= *st.begin();
for(int i=1;i<=n;i++)dst[i]=0;
P={0,0};
dfs(a,0);
int x=P.ss;
for(int i=1;i<=n;i++)dst[i]=0;
P={0,0};
dfs(x,0);
int y=P.ss;
vis[y]=vis[x]=1;
st.erase(y);
st.erase(x);
ans+=dst[y]*2-2;
vc.pb({x,y});
ANS[x]=y;
ANS[y]=x;
}
cout<<ans<<" "<<ans<<endl;
if(st.size()){
int z=*st.begin();
int x=vc[0].ff,y=vc[0].ss;
ANS[x]=z;
ANS[y]=x;
ANS[z]=y;
}
for(int i=1;i<=n;i++)cout<<ANS[i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++)cout<<ANS[i]<<" ";
}
