#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int n , mini , maxi , fth , centroid;
int which[DIMN] , wm[DIMN] , sub[DIMN] , under[DIMN];
vector <int> v[DIMN] , su , supra;
void dfs (int nod , int tt){
int i , vecin , ok = 1;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i];
if (vecin != tt){
dfs (vecin , nod);
sub[nod] += sub[vecin] + 1;
if (sub[vecin] + 1 > n / 2)
ok = 0;
}
}
if (n - sub[nod] - 1 > n / 2)
ok = 0;
if (ok && !centroid){
centroid = nod;
fth = tt;
}
maxi = maxi + 2 * min(sub[nod] + 1 , n - 1 - sub[nod]);
if (which[nod] == nod){ /// nu l ai schimbat inca
if (tt){
swap(which[nod] , which[tt]);
mini += 2;
}
else {
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i];
if (vecin != tt){
swap(which[vecin] , which[nod]);
mini += 2;
break;
}
}
}
}
}
void dfs2 (int nod , int tt){
int i , vecin;
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i];
if (vecin != tt){
dfs2 (vecin , nod);
under[vecin] = 1;
}
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int x , y , i;
fscanf (fin,"%d",&n);
for (i = 1 ; i < n ; i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
/// solve pentru minim
mini = 0;
for (i = 1 ; i <= n ; i++){
which[i] = i; /// ce nod e acum in locul in care se afla nodul i?
wm[i] = i;
}
dfs (1 , 0);
fprintf (fout,"%d %d\n" , mini , maxi);
for (i = 1 ; i <= n ; i++)
fprintf (fout,"%d ",which[i]);
fprintf (fout,"\n");
dfs2 (centroid , fth);
for (i = 1 ; i <= n ; i++){
if (under[i])
su.push_back(i);
else if (i != centroid)
supra.push_back(i);
}
while (!su.empty() && !supra.empty()){
swap(wm[su.back()] , wm[supra.back()]);
su.pop_back();
supra.pop_back();
}
for (i = 0 ; i < v[centroid].size() ; i++){
int vecin = v[centroid][i];
swap(wm[centroid] , wm[vecin]);
break;
}
for (i = 1 ; i <= n ; i++)
fprintf (fout,"%d ",wm[i]);
return 0;
}
