// File village.cpp created on 16.10.2025 at 20:35:16
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int max_N = int(1E5) + 5;
int N;
std::vector<int> adj[max_N];
i64 ans1 = 0;
int go[max_N];
int ord1[max_N];
void dfs1(int v, int pr) {
for (auto u : adj[v]) {
if (u == pr) {
continue;
}
dfs1(u, v);
if (go[u] == u) {
std::swap(go[u], go[v]);
ans1 += 2;
}
}
if (pr == -1 && go[v] == v) {
std::swap(go[v], go[adj[v][0]]);
ans1 += 2;
}
}
int siz[max_N];
void dfs2(int v, int pr) {
siz[v] = 1;
for (auto u : adj[v]) {
if (u == pr) {
continue;
}
dfs2(u, v);
siz[v] += siz[u];
}
}
int tin[max_N];
int tord[max_N];
int ord2[max_N];
int tim = 0;
void dfs3(int v, int pr) {
tin[v] = tim;
tord[tim++] = v;
for (auto u : adj[v]) {
if (u == pr) {
continue;
}
dfs3(u, v);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N;
for (int i = 1; i < N; ++i) {
int A, B;
std::cin >> A >> B;
--A, --B;
adj[A].emplace_back(B);
adj[B].emplace_back(A);
}
for (int i = 0; i < N; ++i) {
go[i] = i;
}
dfs1(0, -1);
for (int i = 0; i < N; ++i) {
ord1[i] = go[i];
}
dfs2(0, -1);
i64 ans2 = 0;
for (int i = 1; i < N; ++i) {
ans2 += std::min(siz[i], N - siz[i]) * 2;
}
int centro = 0;
while (true) {
int ncentro = -1;
for (auto u : adj[centro]) {
if (siz[u] > siz[centro]) {
continue;
}
if (siz[u] * 2 > N) {
ncentro = u;
break;
}
}
if (ncentro == -1) {
break;
}
centro = ncentro;
}
debug(centro);
dfs3(centro, -1);
for (int i = 0; i < N; ++i) {
ord2[i] = tord[(tin[i] + N / 2) % N];
}
std::cout << ans1 << ' ' << ans2 << '\n';
for (int i = 0; i < N; ++i) {
std::cout << ord1[i] + 1 << " \n"[i == N - 1];
}
for (int i = 0; i < N; ++i) {
std::cout << ord2[i] + 1 << " \n"[i == N - 1];
}
return 0;
}
