#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
const int MXN = 1e5+5;
int n;
vi adj[MXN];
int deg[MXN];
int mn_ans[MXN], mx_ans[MXN];
ll mn_swap, mx_swap;
int sz[MXN], H[MXN];
void dfs(int u, int p) {
sz[u] = 1;
for(int v : adj[u]) if(v != p) {
dfs(v, u); sz[u] += sz[v];
}
}
int centroid(int u, int p) {
for(int v : adj[u]) if(v != p) {
if(2*sz[v] > n) return centroid(v, u);
}
return u;
}
void dfs1(int u, int p, vi &arr) {
H[u] = H[p]+1;
arr.PB(u);
for(int v : adj[u]) if(v != p) dfs1(v, u, arr);
}
int main() {
cin >> n;
for(int i = 1; i < n; i++) {
int a, b; cin >> a >> b;
adj[a].PB(b);
adj[b].PB(a);
deg[a]++, deg[b]++;
}
{
// min
queue<int> Q;
for(int i = 1; i <= n; i++) {
if(deg[i] == 1) {
Q.push(i);
}
}
iota(mn_ans+1, mn_ans+n+1, 1);
while(!Q.empty()) {
int i = Q.front(); Q.pop();
if(i != mn_ans[i]) continue;
deg[i] = 0;
bool found = false;
for(int j : adj[i]) {
if(deg[j] > 0) {
deg[j] = 0; found = true;
for(int t : adj[j]) {
if(deg[t] > 0) {
deg[t]--;
if(deg[t] == 1) {
Q.push(t);
}
}
}
swap(mn_ans[i], mn_ans[j]);
mn_swap += 2;
break;
}
}
if(!found) {
int j = adj[i].back();
swap(mn_ans[i], mn_ans[j]);
mn_swap += 2;
}
}
}
{
// max
dfs(1, 1);
int c = centroid(1, -1);
vi arr = {c};
for(int u : adj[c]) {
dfs1(u, c, arr);
}
for(int i = 1; i <= n; i++) {
mx_swap += 2*H[i];
}
for(int i = 0; i < n; i++) {
mx_ans[arr[i]] = arr[(i+(n+1)/2)%n];
}
}
cout << mn_swap << " " << mx_swap << "\n";
for(int i = 1; i <= n; i++) cout << mn_ans[i] << " \n"[i == n];
for(int i = 1; i <= n; i++) cout << mx_ans[i] << " \n"[i == n];
return 0;
}
