#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> adj(n);
for (int i = 1; i < n; i++) {
int x; cin >> x; x--;
int y; cin >> y; y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
vector<int> amin(n), amax(n);
iota(amin.begin(), amin.end(), 0);
int ansmin = 0;
int64_t ansmax = 0;
auto dfs = [&](auto dfs, int x, int p) -> bool {
vector<int> b;
for (int y : adj[x]) {
if (y != p) {
if (dfs(dfs, y, x)) {
b.push_back(y);
}
}
}
if (b.empty()) {
return 1;
}
ansmin += b.size() * 2;
if (b.size() % 2 == 1) {
swap(amin[x], amin[b[0]]);
for (int i = 1; i < b.size(); i += 2) {
swap(amin[b[i]], amin[b[i + 1]]);
}
} else {
swap(amin[x], amin[b[0]]);
swap(amin[x], amin[b[1]]);
for (int i = 2; i < b.size(); i += 2) {
swap(amin[b[i]], amin[b[i + 1]]);
}
}
return 0;
};
if (dfs(dfs, 0, -1)) {
swap(amin[0], amin[adj[0][0]]);
ansmin += 2;
}
vector<int> sz(n);
auto init = [&](auto init, int x, int p) -> void {
sz[x] = 1;
for (int y : adj[x]) {
if (y != p) {
init(init, y, x);
sz[x] += sz[y];
}
}
ansmax += 2 * min(sz[x], n - sz[x]);
};
auto find = [&](auto find, int x, int p) -> int {
for (int y : adj[x]) {
if (y != p && sz[y] * 2 > n) {
return find(find, y, x);
}
}
return x;
};
init(init, 0, -1);
int c = find(find, 0, -1);
vector<int> b;
auto dfs2 = [&](auto dfs2, int x, int p) -> void {
b.push_back(x);
for (int y : adj[x]) {
if (y != p) {
dfs2(dfs2, y, x);
}
}
};
dfs2(dfs2, 0, -1);
for (int i = 0; i < n; i++) {
amax[b[i]] = b[(i + n / 2) % n];
}
cout << ansmin << " " << ansmax << "\n";
for (int i = 0; i < n; i++) {
cout << amin[i] + 1 << " \n"[i == n - 1];
}
for (int i = 0; i < n; i++) {
cout << amax[i] + 1 << " \n"[i == n - 1];
}
return 6/22;
}
