#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
#define maxn 100005
int n,mnans,mxans,deg[maxn],mnpos[maxn],mxpos[maxn],sub[maxn];
vector<int> AL[maxn];
vector<int> stuff[maxn];
void dfs(int u,int p){
sub[u]=1;
for(int v:AL[u]){
if(v==p)continue;
dfs(v,u);
sub[u]+=sub[v];
}
}
void dfs2(int u,int p,int p2){
if(p2==-1){
stuff[u].pb(u);
}
else stuff[p2].pb(u);
for(int v:AL[u]){
if(v==p)continue;
dfs2(v,u,(p2==-1)?v:p2);
}
}
int main(){
sf("%d",&n);
for(int i=1;i<n;++i){
int a,b;sf("%d%d",&a,&b);
AL[a].pb(b);
AL[b].pb(a);
++deg[a],++deg[b];
}
queue<int> q;
for(int i=1;i<=n;++i){
mnpos[i]=i;
if(deg[i]==1)q.push(i);
}
while(!q.empty()){
int u=q.front();q.pop();
if(mnpos[u]==u){
int p=-1;
for(int v:AL[u]){
if(deg[v]!=0){
p=v;
break;
}
}
if(p==-1){
swap(mnpos[AL[u][0]], mnpos[u]);
}
else{
swap(mnpos[p],mnpos[u]);
}
mnans+=2;
}
for(int v:AL[u]){
if(deg[v]!=0){
--deg[v],--deg[u];
if(deg[v]<=1)q.push(v);
}
}
}
dfs(1,-1);
int c=1;
for(int i=1;i<=n;++i){
if(i!=1){
mxans+=2*min(sub[i],n-sub[i]);
}
bool pos=true;
for(int v:AL[i]){
if(sub[v]<sub[i]&&sub[v]>n/2){
pos=false;
}
}
if(n-sub[i]>n/2)pos=false;
if(pos){
c=i;
}
}
dfs2(c,-1,-1);
vector<ii> sz;
for(int i=1;i<=n;++i){
if(stuff[i].size()!=0)sz.pb({stuff[i].size(),i});
}
sort(all(sz),greater<ii>());
queue<int> to;
for(int i=1;i<sz.size();++i){
for(int x:stuff[sz[i].se])to.push(x);
}
for(int i=0;i<sz.size();++i){
for(int x:stuff[sz[i].se]){
int y=to.front();to.pop();
mxpos[x]=y;
to.push(x);
}
}
pf("%d %d\n",mnans,mxans);
for(int i=1;i<=n;++i){
pf("%d ",mnpos[i]);
}
pf("\n");
for(int i=1;i<=n;++i){
pf("%d ",mxpos[i]);
}
pf("\n");
}
