#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int nax = 200005;
int rep[nax], par[nax], N, sz[nax];
bool swp[nax];
vector<int> G[nax], tab, pos;
void dfs(int u, int f) {
par[u] = f;
tab.push_back(u);
for (auto v : G[u]) {
if (v == f) continue;
dfs(v, u);
}
}
pair<int, vector<int>> smallest() {
for (int i = 1; i <= N; i++) {
rep[i] = i;
swp[i] = false;
par[i] = -1;
}
dfs(1, -1);
reverse(tab.begin(), tab.end());
int ans = 0;
for (auto u : tab) {
if (swp[u] == false) {
int v = par[u];
if (v == -1) v = G[u][0];
swp[u] = swp[v] = true;
swap(rep[u], rep[v]);
ans += 2;
}
}
tab.clear();
for (int i = 1; i <= N; i++)
pos.push_back(rep[i]);
return { ans, pos };
}
i64 sum = 0;
void dfs_size(int u, int f) {
tab.push_back(u);
sz[u] = 1;
for (auto v : G[u]) {
if (v == f) continue;
dfs_size(v, u);
sz[u] += sz[v];
}
sum += 2LL * min(sz[u], (N - sz[u]));
}
int find_centroid(int u, int f) {
for (auto v : G[u]) {
if (v == f) continue;
if (2 * sz[v] > N)
return find_centroid(v, u);
}
return u;
}
pair<i64, vector<int>> largest() {
dfs_size(1, -1);
int root = find_centroid(1, -1);
tab.clear(); pos.clear();
sum = 0;
dfs_size(root, -1);
for (int i = 0; i < N; i++)
rep[tab[i]] = tab[(i + N / 2) % N];
for (int i = 1; i <= N; i++)
pos.push_back(rep[i]);
return { sum, pos };
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
for (int i = 1; i <= N - 1; i++) {
int u, v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
auto A = smallest();
auto B = largest();
cout << A.first << ' ' << B.first << '\n';
for (auto o : A.second) cout << o << " \n"[o == A.second.back()];
for (auto o : B.second) cout << o << " \n"[o == B.second.back()];
}
