#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;cin>>n;
vector<vector<int>> adj(n);
vector<int> d(n);
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;u--,v--;
adj[u].push_back(v);
adj[v].push_back(u);
d[u]++,d[v]++;
}
int ans_mi=0;
vector<int>p_mi(n,-1);
{
vector<unordered_set<int>> adjc(n);
for(int i=0;i<n;i++)adjc[i].insert(begin(adj[i]),end(adj[i]));
vector<vector<int>> ch(n);
vector<int> vis(n),leaf;
for(int i=0;i<n;i++)if(d[i]==1)leaf.push_back(i);
while(ssize(leaf)){
vector<int> nl;
ans_mi+=ssize(leaf);
for(int i:leaf){
// cerr<<"LEAF = "<<i<<endl;
if(ssize(ch[i])){
ans_mi+=ssize(ch[i])-1;
p_mi[ch[i][0]]=i;
for(int j=0;j<ssize(ch[i])-1;j++)p_mi[ch[i][j+1]]=ch[i][j];
p_mi[i]=ch[i].back();
d[i]--;
if (ssize(adjc[i])) {
int v=*adjc[i].begin();
adjc[v].erase(i);
adjc[i].erase(adjc[i].begin());
d[v]--;
// assert(d[i]==0);
if(d[v]==1)nl.push_back(v);
}
} else if (ssize(adjc[i])) {
ch[*adjc[i].begin()].push_back(i);
d[i]--;
int v=*adjc[i].begin();
adjc[v].erase(i);
adjc[i].erase(adjc[i].begin());
d[v]--;
// assert(d[i]==0);
if(d[v]==1)nl.push_back(v);
} else {
d[i]--;
ans_mi++;
int v=*adj[i].begin();
p_mi[i]=p_mi[v];
p_mi[v]=i;
}
}
leaf=nl;
}
}
ll ans_ma=0;
vector<int>p_ma(n,-1);
{
vector<int> sz(n);
auto dfs=[&](auto&& self, int u,int p)->int{
sz[u]=1;
for(int&i:adj[u])if(i!=p)sz[u]+=self(self,i,u);
if(u!=0)ans_ma+=2*min(sz[u],n-sz[u]);
return sz[u];
};
dfs(dfs,0,-1);
int p=-1;
int u=0;
while(1) {
int f=1;
for(int v:adj[u])if(v!=p&&sz[v]>n/2){f=1,p=u,u=v;break;}
if(f)break;
}
vector<int> ord;
auto df=[&](auto&& self,int u,int p)->void{
ord.push_back(u);
for(int i:adj[u])if(i!=p)self(self,i,u);
};
df(df,u,-1);
for(int i=0;i<n;i++)p_ma[ord[i]]=ord[(i+n/2)%n];
}
cout<<ans_mi<<' '<<ans_ma<<'\n';
for(int i:p_mi)cout<<i+1<<' ';
cout<<'\n';
for(int i:p_ma)cout<<i+1<<' ';
cout<<'\n';
}
