#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int n , mini , maxi , fth , centroid;
int which[DIMN] , wm[DIMN] , sub[DIMN] , f[DIMN];
vector <int> v[DIMN] , w[DIMN];
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 poz){
int i , vecin;
f[nod] = 1;
w[poz].push_back(nod);
for (i = 0 ; i < v[nod].size() ; i++){
vecin = v[nod][i];
if (!f[vecin]){
if (nod == centroid)
poz++;
dfs2 (vecin , poz);
}
}
}
int cmp (vector <int> a , vector <int> b){
return a.size() > b.size();
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int x , y , i , a , b , elem;
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 , 1);
a = 1;
b = 2;
elem = v[centroid].size();
swap(w[1] , w[elem + 1]);
sort (w + 1 , w + elem + 1 , cmp);
while (a != b && a <= elem && b <= elem){
swap(wm[w[a].back()] , wm[w[b].back()]);
w[a].pop_back();
w[b].pop_back();
if (w[a].empty()){
while (a <= elem){
if (!w[a].empty())
break;
a++;
}
if (a > elem)
break;
}
b = max(b , a + 1);
while (b <= elem){
if (!w[b].empty())
break;
b++;
}
if (b > elem)
break;
}
/// momentan ai pus tot ce era de pus
int ok = 1;
for (i = 1 ; i <= elem ; i++){
if (!w[i].empty()){
ok = 0;
swap(wm[centroid] , wm[w[i][0]]);
break;
}
}
if (ok){
if (centroid == 1){
swap(wm[centroid] , wm[2]);
}
else swap(wm[centroid] , wm[centroid - 1]);
}
for (i = 1 ; i <= n ; i++)
fprintf (fout,"%d ",wm[i]);
return 0;
}
