/**
* author: wxhtzdy
* created: 20.07.2022 21:10:18
**/
/*
https://codeforces.com/contest/1387/submission/92450554
https://codeforces.com/contest/1387/submission/137586993
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<pair<long long, vector<int>>> ans;
{
vector<int> p(n);
iota(p.begin(), p.end(), 0);
int cnt = 0;
function<void(int, int)> Dfs = [&](int v, int pr) {
for (int u : g[v]) {
if (u != pr) {
if (p[u] == u) {
Dfs(u, v);
if (p[u] == u) {
cnt += 2;
swap(p[v], p[u]);
}
}
}
}
};
Dfs(0, 0);
if (p[0] == 0) {
cnt += 2;
swap(p[0], p[g[0][0]]);
}
ans.emplace_back(cnt, p);
}
{
int root;
vector<int> sz(n);
function<void(int, int)> Dfs = [&](int v, int pr) {
sz[v] = 1;
int mx = 0;
for (int u : g[v]) {
if (u != pr) {
Dfs(u, v);
sz[v] += sz[u];
mx = max(mx, sz[u]);
}
}
if (mx * 2 < n && sz[v] * 2 >= n) {
root = v;
}
};
Dfs(0, 0);
long long cnt = 0;
vector<int> a;
Dfs = [&](int v, int pr) {
a.push_back(v);
sz[v] = 1;
for (int u : g[v]) {
if (u != pr) {
Dfs(u, v);
sz[v] += sz[u];
cnt += sz[u] * 2;
}
}
};
Dfs(root, root);
vector<int> b(n);
for (int i = 0; i < n; i++) {
b[a[i]] = a[(i + n / 2) % n];
}
ans.emplace_back(cnt, b);
}
cout << ans[0].first << " " << ans[1].first << '\n';
for (int j = 0; j < 2; j++) {
for (int i = 0; i < n; i++) {
cout << ans[j].second[i] + 1 << " \n"[i == n - 1];
}
}
return 0;
}
