#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
typedef pair <int, int> pii;
typedef pair <int, bool> pib;
typedef pair <int, pair <int, int> > pip;
typedef pair <pair <int, int>, int> ppi;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define MP make_pair
#define rep(i,a,b) for (long long i=(a);i<(b);i++)
#define rrep(i,a,b) for (long long i=(a);i>(b);i--)
#define SZ(x) ((long long) sizeof(x))
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fileinp freopen("ain.txt","r",stdin);freopen("aout.txt","w",stdout);
const int dx[]={1,-1 ,0,0,1,-1,-1,1};
const int dy[]={0,0,1,-1,-1,-1,1,1};
const int mod=1e9+7;
const int mod2=998244353;
const int INF=(int)1e18;
const int N=100005;
int n,a,b,minans,maxans,cur,ct=1,curval;
int nb[N],minarr[N],maxarr[N],subtree[N];
bool check;
vector<int>adj[N],adj2[N];
vector<pii>temp;
void dfs(int x,int p){
subtree[x]=1;
for(auto it:adj[x]){
if(it!=p){
dfs(it,x);
subtree[x]+=subtree[it];
}
}
}
void dfs2(int x,int p,int chk){
//root tree at centroid
//adj2 is only for layer under centroid and itself
if(chk==-1){
adj2[x].pb(x);
}else{
adj2[chk].pb(x);
}
for(auto it:adj[x]){
if(it!=p){
dfs2(it,x,chk==-1?it:chk);
}
}
}
signed main(){
fastio;
//fileinp;
cin>>n;
rep(i,0,n-1){
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
nb[a]++;nb[b]++;
}
queue<int>q;
rep(i,1,n+1){
minarr[i]=i;
if(nb[i]==1){ //leaf
q.push(i);
}
}
while(!q.empty()){
cur=q.front();
q.pop();
if(minarr[cur]==cur){
curval=-1;
for(auto it:adj[cur]){
if(nb[it]!=0){
curval=it;
break;
}
}
if(curval==-1){
swap(minarr[cur],minarr[adj[cur][0]]);
}else if(curval!=-1){
swap(minarr[cur],minarr[curval]);
}
minans+=2;
}
for(auto it:adj[cur]){
if(nb[it]!=0){
nb[it]--;nb[cur]--;
if(nb[it]<=1){
q.push(it);
}
}
}
}
dfs(1,-1);
ct=1;
rep(i,1,n+1){
if(i>1){
maxans+=2*(min(subtree[i],n-subtree[i]));
}
check=0;
for(auto it:adj[i]){
if(subtree[it]<subtree[i]&&subtree[it]>n/2){
check=1;
}
}
if(n-subtree[i]>n/2){
check=1;
}
if(!check){
ct=i;//centroid
}
}
//cout<<ct<<'\n';
dfs2(ct,-1,-1);
rep(i,1,n+1){
if(adj2[i].size()>0){
temp.pb(MP(adj2[i].size(),i));
}
}
sort(all(temp),greater<pii>());
queue<int>q2;
rep(i,1,temp.size()){ //skip 0 (biggest subtree)
for(auto it:adj2[temp[i].se]){
q2.push(it);
}
}
rep(i,0,temp.size()){
for(auto it:adj2[temp[i].se]){
cur=q2.front();
q2.pop();
maxarr[it]=cur;
//cout<<it<<' '<<cur<<'\n';
q2.push(it);
}
}
cout<<minans<<' '<<maxans<<'\n';
rep(i,1,n+1){
cout<<minarr[i]<<' ';
}
cout<<'\n';
rep(i,1,n+1){
cout<<maxarr[i]<<' ';
}
return 0;
}
