// 23 - 12 - 23
#include<bits/stdc++.h>
using namespace std;
#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"
#define ii pair<int,int>
#define X first
#define Y second
const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;
int n;
vector<int> adj[MAX];
int minx,maxx;
int idx[MAX],idy[MAX];
vector<int> topo;
int siz[MAX];
void dfs(int u = 1,int p = -1){
topo.push_back(u);
siz[u] = 1;
for(auto v : adj[u]){
if(v == p)continue;
dfs(v,u);
siz[u] += siz[v];
maxx += min(n - siz[v],siz[v]);
}
if(idx[u] == u){
if(p == -1)swap(idx[u],idx[adj[u][0]]);
else swap(idx[u],idx[p]);
minx += 2;
}
}
signed main(){
read();
cin >> n;
for(int i = 1,u,v;i < n;i++){
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1;i <= n;i++){
idx[i] = i;
idy[i] = i;
}
//topo.push_back(0);
dfs();
for(int i = 1;i <= n;i++){
idy[topo[i - 1]] = topo[(i - 1 + n / 2) % n];
}
cout << minx << " " << maxx * 2 << '\n';
for(int i = 1;i <= n;i++)cout << idx[i] << " \n"[i == n];
for(int i = 1;i <= n;i++)cout << idy[i] << " \n"[i == n];
}
