#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
vector<vector<int>> neigh;
vector<int> sz;
vector<int> v_mn_ans;
vector<int> v_mx_ans;
vector<vector<int>> ch;
int n;
int mn_ans=0;
int mx_ans=0;
int find_mn(int x, int p){
sz[x]=1;
vector<int> v;
for (auto u : neigh[x])
{
if(u==p) continue;
int fm=find_mn(u,x);
sz[x]+=sz[u];
if(fm!=-1) v.push_back(fm);
}
v.push_back(x);
if(sz(v)==1) return v[0];
for (int i = 0; i < sz(v); i++)
{
v_mn_ans[v[i]]=v[(int)((i+1)%(int)sz(v))];
mn_ans+=2-(v[i]==x||v[(i+1)%sz(v)]==x);
}
return -1;
}
void find_mx(int x, int p, int d, int indx){
ch[indx].push_back(x);
mx_ans+=d*2;
for (auto u : neigh[x])
{
if(u==p) continue;
find_mx(u,x,d+1,indx);
}
}
int find_centroid(int x, int p){
for (auto u : neigh[x])
{
if(u==p) continue;
if(sz[u]>n/2) return find_centroid(u,x);
}
return x;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
neigh.resize(n);
sz.resize(n,1);
v_mn_ans.resize(n,-1);
v_mx_ans.resize(n,-1);
for (int i = 0; i < n-1; i++)
{
int a,b; cin >> a >> b;
neigh[a-1].push_back(b-1);
neigh[b-1].push_back(a-1);
}
int rt=0;
for (int i = 0; i < n; i++) { if(sz(neigh[i])==1) rt=neigh[i][0]; }
find_mn(rt,rt);
int centr=find_centroid(rt,rt);
ch.resize(sz(neigh[centr]));
for (int i = 0; i < sz(neigh[centr]); i++)
{
find_mx(neigh[centr][i],centr,1,i);
}
sort(all(ch),[](vector<int> a, vector<int> b){
if(sz(a)>sz(b)) return true;
return false;
});
int l=0;
int r=sz(ch)-1;
int li=0;
int ri=sz(ch[r])-1;
int t=0;
while(l<r||(l==r&&li<ri)){
if(ri==-1) { r--, ri=sz(ch[r])-1; continue; }
if(li==sz(ch[l])) { li=0, l++; continue; }
if(t%2==0){
v_mx_ans[ch[l][li]]=ch[r][ri];
li++;
}else{
v_mx_ans[ch[r][ri]]=ch[l][li];
ri--;
}
t++;
}
if(t%2==0){
v_mx_ans[ch[l][li]]=centr;
v_mx_ans[centr]=ch[0][0];
}else{
v_mx_ans[ch[r][ri]]=centr;
v_mx_ans[centr]=ch[0][0];
}
//mx_ans--;
cout << mn_ans << " " << mx_ans << "\n";
for (int i = 0; i < n; i++) cout << v_mn_ans[i]+1 << " ";
cout << "\n";
for (int i = 0; i < n; i++) cout << 1 << " ";
return 0;
}
