#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;
int deg[N];
set<int>st[N];
int ans[N];
vector<int>v[N];
int n;
vector<int>rt;
int s2=0;
int sbtr[N];
void dfs(int a, int p){
rt.pb(a);
sbtr[a]=1;
for(auto b:v[a]){
if(b==p)continue;
dfs(b,a);
sbtr[a]+=sbtr[b];
s2+=2*min(sbtr[b], n - sbtr[b]);
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
ans[i]=i;
}
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
st[a].insert(b);
v[a].pb(b);
v[b].pb(a);
st[b].insert(a);
deg[a]++;
deg[b]++;
}
set<int>lf;
for(int i=1;i<=n;i++){
if(deg[i]==1){
lf.insert(i);
}
}
int cnt=0;
int s=0;
while(cnt<n){
cnt+=lf.size();
vector<int>add;
for(auto a:lf){
int p;
if(st[a].empty()){
p=v[a][0];
}
else p= *st[a].begin();
if(ans[a]==a){
swap(ans[a],ans[p]);
s+=2;
}
deg[p]--;
deg[a]--;
st[a].erase(p);
st[p].erase(a);
if(deg[p]==1){
add.pb(p);
}
}
lf.clear();
for(auto x:add){
lf.insert(x);
}
}
dfs(1,0);
cout<<s<<" "<<s2<<endl;
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
for(int i = 0; i < n; i++){
ans[rt[i]]=rt[(i+n/2)%n];
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
}
