#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
template<class T>bool minimize(T& a, T b){
if(a > b){
a = b;
return true;
}
return false;
}
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
const int lim = 1e5 + 5;
const int INF = 1e9;
int n;
vector<int>g[lim];
namespace sub1{
void solve(){
vector<vector<int>>dis(n + 1, vector<int>(n + 1));
function<void(const int, int, int)>dfs;
dfs = [&] (const int root, int s, int p){
for(int& d : g[s]){
if(d != p){
dis[root][d] = dis[root][s] + 1;
dfs(root, d, s);
}
}
};
for(int i = 1; i <= n; i++){
dfs(i, i, dis[i][i] = 0);
}
vector<int>p(n), ami(n), ama(n);
int val_mi = INF, val_ma = -INF;
iota(p.begin(), p.end(), 0);
do{
bool flag = true;
int sum = 0;
for(int i = 0; i < n; i++){
if(i == p[i]){
flag = false;
break;
}
sum += dis[i + 1][p[i] + 1];
}
if(flag){
if(minimize(val_mi, sum)){
ami = p;
}
if(maximize(val_ma, sum)){
ama = p;
}
}
} while(next_permutation(p.begin(), p.end()));
cout << val_mi << " " << val_ma << "\n";
for(int& i : ami){
cout << i + 1 << " ";
}
cout << "\n";
for(int& i : ama){
cout << i + 1 << " ";
}
}
}
namespace sub23{
int vmin = 0, par[lim], pmax[lim], pmin[lim], siz[lim];
ll vmax = 0;
vector<int>tour;
void dfs(int s){
tour.push_back(s);
siz[s] = 1;
for(int& d : g[s]){
if(d != par[s]){
par[d] = s;
dfs(d);
siz[s] += siz[d];
vmax += min(siz[d], n - siz[d]);
}
}
}
void solve(){
par[1] = 0;
dfs(1);
for(int i = 0; i < n; i++){
pmax[tour[i]] = tour[(i + (n >> 1)) % n];
}
reverse(tour.begin(), tour.end());
vector<bool>proc(n + 1, false);
iota(pmin + 1, pmin + n + 1, 1);
for(int& i : tour){
if(!proc[i]){
vmin += 2;
int j = par[i];
if(j == 0){
j = g[1][0];
}
swap(pmin[i], pmin[j]);
proc[j] = true;
}
}
cout << vmin << " " << (vmax << 1LL) << "\n";
for(int i = 1; i <= n; i++){
cout << pmin[i] << " ";
}
cout << "\n";
for(int i = 1; i <= n; i++){
cout << pmax[i] << " ";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
if(n <= 10){
sub1::solve();
}
else{
sub23::solve();
}
}
