// 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 int long long
#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 mxc[MAX];
int siz[MAX];
int mic[MAX];
int low = 0,high = 0;
vector<int> rt;
void dfs(int u = 1,int p = -1){
siz[u] = 1;
rt.push_back(u);
for(auto v : adj[u]){
if(v == p)continue;
dfs(v,u);
siz[u] += siz[v];
high += min(n - siz[v],siz[v]);
}
if(u == mic[u]){
if(p == -1)swap(mic[u],mic[adj[u][0]]);
else swap(mic[u],mic[p]);
low += 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++){
mic[i] = i;
mxc[i] = i;
}
dfs();
for(int i = 1;i <= n;i++){
int u = rt[i - 1];
int v = rt[(i - 1 + n / 2) % n];
mxc[u] = v;
}
cout << low << " " << high * 2 << '\n';
for(int i = 1;i <= n;i++)cout << mic[i] << " \n"[i == n];
for(int i = 1;i <= n;i++)cout << mxc[i] << " \n"[i == n];
}
