#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int n , mini , fth , centroid;
long long maxi;
int which[DIMN] , wm[DIMN] , sub[DIMN] , f[DIMN];
vector <int> v[DIMN] , w[DIMN];
priority_queue <pair <int , int> > h;
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;
if (nod != centroid)
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 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 %lld\n" , mini , maxi);
for (i = 1 ; i <= n ; i++)
fprintf (fout,"%d ",which[i]);
fprintf (fout,"\n");
dfs2 (centroid , 0);
a = 1;
b = 2;
elem = v[centroid].size();
for (i = 1 ; i <= elem ; i++)
h.push(make_pair(w[i].size() , i));
while (h.size() >= 2){
a = h.top().second;
h.pop();
b = h.top().second;
h.pop();
swap(wm[w[a].back()] , wm[w[b].back()]);
w[a].pop_back();
w[b].pop_back();
if (w[a].size())
h.push(make_pair(w[a].size() , a));
if (w[b].size())
h.push(make_pair(w[b].size() , b));
}
if (h.empty()){
if (centroid == 1){
swap(wm[centroid] , wm[2]);
}
else swap(wm[centroid] , wm[centroid - 1]);
}
else {
a = h.top().second;
swap(wm[w[a].back()] , wm[centroid]);
}
for (i = 1 ; i <= n ; i++){
fprintf (fout,"%d ",wm[i]);
}
return 0;
}
