#include<bits/stdc++.h>
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 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(){
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);
}
sub23::solve();
}
