#include <bits/stdc++.h>
#define int long long
#define float long double
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define f first
#define s second
#define ve vector
#define emb emplace_back
#define em emplace
using namespace std;
const int inf = 1e18;
const int mod = 1e9 + 7;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
ve<ve<int>> adj(n);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].emb(v), adj[v].emb(u);
}
int mn = 0, mx = 0;
ve<int> mnans(n), mxans(n);
queue<int> q;
ve<int> par(n, -1), in(n, 0);
ve<bool> rem(n, false);
q.em(0);
while (!q.empty()) {
int t = q.front();
q.pop();
for (auto &e : adj[t]) {
if (e == par[t]) continue;
par[e] = t, q.em(e);
}
}
for (int i = 0; i < n; i++) {
mnans[i] = i;
in[i] = adj[i].size();
if (adj[i].size() == 1) q.em(i);
}
while (!q.empty()) {
int t = q.front();
q.pop();
if (rem[t] || par[t] == -1 || rem[par[t]]) continue;
swap(mnans[t], mnans[par[t]]), mn += 2;
for (auto &e : adj[t]) in[e]--;
for (auto &e : adj[par[t]]) in[e]--;
rem[t] = rem[par[t]] = true;
if (par[par[t]] != -1 && !rem[par[par[t]]] && in[par[par[t]]] == 1) q.em(par[par[t]]);
}
for (int i = 0; i < n; i++) {
if (mnans[i] != i) continue;
swap(mnans[i], mnans[adj[i][0]]), mn += 2;
}
ve<int> sz(n, 0);
function<int(int)> getsz = [&](int x) {
int res = 1;
for (auto &e : adj[x]) {
if (e == par[x]) continue;
res += getsz(e);
}
return sz[x] = res;
};
function<int(int)> centroid = [&](int x) {
for (auto &e : adj[x]) {
if (e == par[x]) continue;
if (sz[e] * 2 > n) return centroid(e);
}
return x;
};
getsz(0);
int cen = centroid(0);
ve<int> dis(n, -1), ord(n);
dis[cen] = 0, ord[0] = cen;
int timer = 0;
function<void(int, int)> dfs = [&](int x, int p) {
for (auto &e : adj[x]) {
if (e == p) continue;
dis[e] = dis[x] + 1, ord[++timer] = e;
dfs(e, x);
}
};
dfs(cen, -1);
for (int i = 0; i < n; i++) mxans[i] = ord[(i+(n/2))%n], mx += 2 * dis[i];
cout << mn << ' ' << mx << '\n';
for (auto &e : mnans) cout << e+1 << ' '; cout << '\n';
for (auto &e : mxans) cout << e+1 << ' ';
}
