#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(args...) fprintf(stderr,args)
const int maxn=3e5+10;
const int inf=1e9+7;
vector<int>v[maxn], aux;
int val[maxn], resp1, qm1[maxn], pai[maxn], sub[maxn], prof[maxn], qm2[maxn], n, resp2;
void dfs(int u){
if(pai[u]!=u) aux.push_back(u);
sub[u]=1;
for(int viz : v[u]){
if(viz==pai[u]) continue;
pai[viz]=u;
prof[viz]=prof[u]+1;
dfs(viz);
sub[u]+=sub[viz];
if(val[viz]==viz){
swap(val[viz],val[u]);
resp1+=2;
}
}
}
int centroide(int u){
for(int viz : v[u]) if(sub[viz]>(n/2)&&viz!=pai[u]) return centroide(viz);
return u;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for(int i=1;i<=n;i++) val[i]=i;
for(int i=1;i<n;i++){
int a, b; cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
pai[1]=1;
dfs(1);
int c=centroide(1);
pai[c]=c; prof[c]=0;
aux.clear();
dfs(c);
int tam=aux.size(), half=tam/2;
for(int i=1;i<=n;i++) resp2+=2*prof[i];
if(n%2){
qm2[aux[0]]=c;
qm2[c]=aux[half];
qm2[aux[half]]=aux[0];
}else{
qm2[c]=aux.back();
qm2[aux.back()]=c;
aux.pop_back();
qm2[aux[0]]=aux[half];
qm2[aux[half]]=aux[0];
}
for(int i=1;i<half;i++){
qm2[aux[i]]=aux[i+half];
qm2[aux[i+half]]=aux[i];
}
if(val[1]==1){
resp1+=2;
swap(val[1],val[v[1][0]]);
}
for(int i=1;i<=n;i++) qm1[val[i]]=i;
cout << resp1 << " " << resp2 << endl;
for(int i=1;i<=n;i++) cout << qm1[i] << " ";
cout << endl;
for(int i=1;i<=n;i++) cout << qm2[i] << " ";
cout << endl;
}
