#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 1e5 + 5;
const int INF = 1e9;
int n;
vector<int>g[lim];
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];
}
cout << vmax << " " << (vmax << 1LL) << "\n";
for(int i = 1; i <= n; i++){
cout << pmax[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);
}
solve();
}
