#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
#define ff first
#define ss second
const int MAXN = 1e5 + 7;
vi graf[MAXN];
int choice1[MAXN];
int choice2[MAXN];
ll ans1 = 0;
ll ans2 = 0;
int sajz[MAXN];
void dfs(int v, int p) {
sajz[v] = 1;
vector<int> synowie;
for (int s : graf[v]) {
if (s != p) {
dfs(s, v);
sajz[v] += sajz[s];
if (!choice1[s]) synowie.push_back(s);
}
}
//cout << v << ' ' << synowie.size() << '\n';
if (synowie.size() == 0) return;
if (synowie.size() % 2 == 0) {
int v2 = synowie.back();
synowie.pop_back();
int v3 = synowie.back();
synowie.pop_back();
choice1[v] = v2;
choice1[v2] = v3;
choice1[v3] = v;
ans1 += 4;
}
else {
choice1[v] = synowie.back();
choice1[synowie.back()] = v;
synowie.pop_back();
ans1 += 2;
}
while (synowie.size()) {
int v2 = synowie.back();
synowie.pop_back();
int v3 = synowie.back();
synowie.pop_back();
choice1[v2] = v3;
choice1[v3] = v2;
ans1 += 4;
}
}
int n;
int find_centr(int v, int p) {
int maxi = n - sajz[v];
for (int s : graf[v]) {
if (s == p) continue;
maxi = max(maxi, sajz[s]);
int v2 = find_centr(s, v);
if (v2) return v2;
}
if (maxi <= n / 2) return v;
return 0;
}
vector<pii> odl[MAXN];
void dfs1(int v1, int v, int p, int g) {
odl[v1].push_back({g, v});
for (int s : graf[v]) {
if (s != p) dfs1(v1, s, v, g + 1);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
int a, b;
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
int v = 1;
for (int i = 1; i <= n; i++) {
if (graf[i].size() == 1) v = i;
}
dfs(v, v);
if (choice1[v] == 0) {
int kto = 1;
for (int v2 = 1; v2 <= n; v2++) {
if (choice1[v2] == graf[v][0]) kto = v2;
}
choice1[kto] = v;
choice1[v] = graf[v][0];
ans1 += 2;
}
int centr = find_centr(v, v);
priority_queue<pair<int, int>> kolejka;
for (int s : graf[centr]) {
dfs1(s, s, centr, 1);
sort(odl[s].begin(), odl[s].end());
kolejka.push({odl[s].size(), s});
// for (auto o : odl[s]) {
// cout << o.ff << ' ' << o.ss << ' ' << s << '\n';
// }
}
// cout << centr << '\n';
int n2 = n;
while (n2 > 3) {
int rep1 = kolejka.top().second;
kolejka.pop();
int rep2 = kolejka.top().second;
kolejka.pop();
int v1 = odl[rep1].back().ss;
int g1 = odl[rep1].back().ff;
int v2 = odl[rep2].back().ss;
int g2 = odl[rep2].back().ff;
//cout << rep1 << ' ' << rep2 << ' ' << v1 << ' ' << g1 << ' ' << v2 << ' ' << g2 << '\n';
odl[rep1].pop_back();
odl[rep2].pop_back();
choice2[v1] = v2;
choice2[v2] = v1;
ans2 += 2 * (g1 + g2);
if (odl[rep1].size()) kolejka.push({odl[rep1].size(), rep1});
if (odl[rep2].size()) kolejka.push({odl[rep2].size(), rep2});
n2 -= 2;
}
if (n2 == 2) {
for (int s : graf[centr]) {
if (!choice2[s]) {
choice2[centr] = s;
choice2[s] = centr;
ans2 += 2;
break;
}
}
}
else if (n2 == 3) {
vector<int> sas;
for (int s : graf[centr]) {
if (!choice2[s]) {
sas.push_back(s);
}
}
choice2[centr] = sas[0];
choice2[sas[0]] = sas[1];
choice2[sas[1]] = centr;
ans2 += 4;
}
cout << ans1 << ' ' << ans2 << '\n';
for (int i = 1; i <= n; i++) {
cout << choice1[i] << ' ';
}
cout << '\n';
for (int i = 1; i <= n; i++) {
cout << choice2[i] << ' ';
}
cout << '\n';
return 0;
}
