#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n;
long long d[maxn], dp[maxn], ans[maxn], ans2[maxn], rez;
vector <int> v[maxn], g[maxn];
int br = 1;
set <pair <int, int> > s;
set <pair <int, int> > ::iterator it;
void dfs (int x, int p){
d[x] = 1;
for (int i = 0; i < v[x].size(); i++){
int y = v[x][i];
if (y != p){
dfs(y, x);
d[x] += d[y];
if (ans2[y] == y){
swap(ans2[y], ans2[x]);
rez += 2;
}
}
}
}
int centroid (int x, int p){
for (int i = 0; i < v[x].size(); i++){
int y = v[x][i];
if (y != p and d[y] * 2 > d[1]) return centroid(y, x);
}
return x;
}
void dfs2 (int x, int p, int gr){
g[gr].push_back(x);
d[x] = 1;
dp[x] = 0;
for (int i = 0; i < v[x].size(); i++){
int y = v[x][i];
if (y != p){
int novig = gr;
if (gr == 0) novig = br, br++;
dfs2(y, x, novig);
dp[x] += dp[y] + d[y];
d[x] += d[y];
}
}
}
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++) ans2[i] = i;
for (int i = 0; i < n - 1; i++){
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, 0);
if (ans2[1] == 1) swap(ans2[1], ans2[v[1][0]]), rez += 2;
int c = centroid(1, 0);
dfs2(c, 0, 0);
cout << rez << " " << dp[c] * 2 << "\n";
for (int i = 1; i <= n; i++) cout << ans2[i] << " ";
cout << "\n";
for (int i = 0; i < br; i++){
s.insert({g[i].size(), i});
}
it = s.end();
it--;
while ((it -> first) > 1){
int in1 = it -> second;
it--;
int in2 = it -> second;
s.erase({g[in1].size(), in1});
s.erase({g[in2].size(), in2});
ans[g[in1][g[in1].size()-1]] = g[in2][g[in2].size()-1];
ans[g[in2][g[in2].size()-1]] = g[in1][g[in1].size()-1];
g[in1].pop_back();
g[in2].pop_back();
s.insert({g[in1].size(), in1});
s.insert({g[in2].size(), in2});
it = s.end();
it--;
}
int prvi = -1, prosli;
for (it = s.begin(); it != s.end(); it++){
if ((it -> first) > 0 and prvi == -1) prvi = it -> second;
else if ((it -> first) > 0){
int tr = it -> second;
ans[g[tr][0]] = g[prosli][0];
}
prosli = it -> second;
}
ans[g[prvi][0]] = g[prosli][0];
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << "\n";
return 0;
}
