#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=1e9;
vector<int> ds[MAXN],adj[MAXN],e[MAXN],ie[MAXN],vx[MAXN],vi;
long long dp[MAXN][3],sub[MAXN],ans1[MAXN],ans2[MAXN],P[MAXN],cnt=0;
set<int> st;
priority_queue< pair<int,int> > pq;
void dfs1(int i,int pre)
{
dp[i][0]=0,dp[i][1]=0,dp[i][2]=INF;
long long mn=INF,sum=0;
vector< pair<int,int> > w;
for(auto v:ds[i]) if(v!=pre)
{
dfs1(v,i);
mn=min(mn,dp[v][2]-dp[v][0]+2);
long long a=dp[i][1]+dp[v][1]+2;
long long b=dp[i][2]+dp[v][1]+2;
long long c=dp[i][2]+dp[v][0];
dp[i][2]=min(a,min(b,c));
if(dp[i][2]==a) w.push_back({1,v});
else if(dp[i][2]==b) w.push_back({2,v});
else w.push_back({3,v});
dp[i][1]+=dp[v][0];
dp[i][0]+=dp[v][0];
}
dp[i][0]+=mn,dp[i][0]=min(dp[i][0],dp[i][2]);
int pos=2;
reverse(w.begin(),w.end());
for(auto v:w) if(pos==2)
{
if(v.first==3) ie[i].push_back(v.second);
else
{
e[i].push_back(v.second);
if(v.first==1) pos=1;
}
}
else ie[i].push_back(v.second);
}
void dfs2(int i,int pre)
{
sub[i]=1;
for(auto v:ds[i]) if(v!=pre)
{
dfs2(v,i);
sub[i]+=sub[v];
}
}
void trace1(int i,int pre,int val)
{
if(!val)
{
if(dp[i][0]==dp[i][2])
{
st.insert(i);
trace1(i,pre,2);
}
else
{
int mn=INF,pos=0;
for(auto v:ds[i]) if(v!=pre&&mn>dp[v][2]-dp[v][0]+2) mn=dp[v][2]-dp[v][0]+2,pos=v;
adj[i].push_back(pos),adj[pos].push_back(i),st.insert(pos);
trace1(pos,i,2);
for(auto v:ds[i]) if(v!=pre&&v!=pos) trace1(v,i,0);
}
}
else if(val==1)
{
for(auto v:ds[i]) if(v!=pre) trace1(v,i,0);
}
else
{
for(auto v:e[i])
{
adj[i].push_back(v),adj[v].push_back(i);
trace1(v,i,1);
}
for(auto v:ie[i]) trace1(v,i,0);
}
}
void dfsus(int i,int pre)
{
vi.push_back(i);
for(auto v:adj[i]) if(v!=pre) dfsus(v,i);
}
long long solve1(int n)
{
dfs1(1,1);
trace1(1,1,0);
for(auto v:st)
{
vi.clear();
dfsus(v,v);
for(int i=0;i<vi.size();i++) ans1[vi[i]]=vi[(i+1)%(int)vi.size()];
}
return dp[1][0];
}
int centroid(int i,int pre,int n)
{
for(auto v:ds[i]) if(v!=pre&&sub[v]*2>n) return centroid(v,i,n);
return i;
}
void dfs3(int i,int pre,int cat)
{
vx[cat].push_back(i);
for(auto v:ds[i]) if(v!=pre)
{
if(!cat) dfs3(v,i,++cnt);
else dfs3(v,i,cat);
}
}
long long solve2(int n)
{
long long ans=0;
dfs2(1,1);
for(int i=2;i<=n;i++) ans+=min(sub[i],n-sub[i])*2;
int pos=centroid(1,1,n);
dfs3(pos,pos,0);
for(int i=0;i<=cnt;i++) pq.push({vx[i].size(),i});
vector<int> per;
int pre=-1;
for(int i=1;i<=n;i++)
{
int a=pq.top().second;
pq.pop();
if(!per.empty()&&a==pre)
{
int b=pq.top().second;
pq.pop();
per.push_back(vx[b].back()),vx[b].pop_back();
if(!vx[b].empty()) pq.push({vx[b].size(),b});
if(!vx[a].empty()) pq.push({vx[a].size(),a});
pre=b;
}
else
{
per.push_back(vx[a].back()),vx[a].pop_back();
if(!vx[a].empty()) pq.push({vx[a].size(),a});
pre=a;
}
}
for(int i=0;i<n;i++) ans2[per[i]]=per[(i+1)%n];
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int l,r;
cin>>l>>r;
ds[l].push_back(r),ds[r].push_back(l);
}
cout<<solve1(n)<<" "<<solve2(n)<<"\n";
for(int i=1;i<=n;i++) cout<<ans1[i]<<" ";
cout<<"\n";
for(int i=1;i<=n;i++) cout<<ans2[i]<<" ";
}
