#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template<class Key, class Compare = less<Key>>
using indexed_set = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
template<class Key, class Value, class Compare = less<Key>>
using indexed_map = tree<Key, Value, Compare, rb_tree_tag, tree_order_statistics_node_update>;
template<class Key>
using hash_set = gp_hash_table<
Key, null_type, hash<Key>, equal_to<Key>, direct_mask_range_hashing<Key>, linear_probe_fn<>,
hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>;
template<class Key, class Value>
using hash_map = gp_hash_table<
Key, Value, hash<Key>, equal_to<Key>, direct_mask_range_hashing<Key>, linear_probe_fn<>,
hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
const time_point start_time;
public:
Timer(): start_time(now()) {}
rep elapsed_time() const {
return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
}
} timer;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<vector<int>> tree(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
vector<int> ans1(n + 1), ans2(n + 1);
auto sol1 = [&] {
vector<int> par(n + 1), deg(n + 1, 0);
vector<bool> vis(n + 1, 0);
auto dfs = [&] (auto self, int u, int p)->void {
par[u] = p;
for (auto &v : tree[u]) {
if (v != p) {
deg[u]++;
self(self, v, u);
}
}
};
dfs(dfs, 1, 0);
queue<int> q;
for (int i = 1; i <= n; i++) {
if (!deg[i]) {
q.push(i);
}
}
vector<pair<int, int>> swaps;
while (q.size()) {
int u = q.front();
q.pop();
if (u == 1) {
swaps.push_back({1, tree[1].back()});
continue;
}
swaps.push_back({u, par[u]});
deg[par[u]]--;
if (par[u] != 1) {
if (!vis[par[u]]) {
deg[par[par[u]]]--;
}
if (!vis[par[par[u]]] && !deg[par[par[u]]]) {
q.push(par[par[u]]);
vis[par[par[u]]] = 1;
}
}
vis[u] = 1;
vis[par[u]] = 1;
}
iota(ans1.begin(), ans1.end(), 0);
for (auto &[u, v] : swaps) {
swap(ans1[u], ans1[v]);
}
return int(swaps.size()) * 2;
};
auto sol2 = [&] {
ll res = 0;
vector<int> sz(n + 1, 1);
auto dfs = [&] (auto self, int u, int p)->void {
for (auto &v : tree[u]) {
if (v != p) {
self(self, v, u);
sz[u] += sz[v];
}
}
};
auto find_centroid = [&] (auto self, int u, int p)->int {
for (auto &v : tree[u]) {
if (v != p && sz[v] > n / 2) {
return self(self, v, u);
}
}
return u;
};
dfs(dfs, 1, 0);
for (int i = 1; i <= n; i++) {
res += ll(2 * min(sz[i], n - sz[i]));
}
int c = find_centroid(find_centroid, 1, 0);
sz = vector<int>(n + 1, 1);
dfs(dfs, c, 0);
int ma = 0, heavy;
for (auto &v : tree[c]) {
if (sz[v] > ma) {
ma = sz[v];
heavy = v;
}
}
int v2 = tree[c].back();
if (n & 1) {
if (v2 == heavy) {
v2 = tree[c].front();
}
ans2[heavy] = c;
ans2[v2] = heavy;
ans2[c] = v2;
}
vector<int> a;
auto dfs2 = [&] (auto self, int u, int p)->void {
if (!(n & 1) || (u != c && u != v2 && u != heavy)) {
a.push_back(u);
}
for (auto &v : tree[u]) {
if (v != p) {
self(self, v, u);
}
}
};
dfs2(dfs2, c, 0);
for (int i = 0; i < int(a.size()) / 2; i++) {
ans2[a[i]] = a[i + int(a.size()) / 2];
ans2[a[i + int(a.size()) / 2]] = a[i];
}
return res;
};
cout << sol1() << " " << sol2() << "\n";
for (int i = 1; i <= n; i++) {
cout << ans1[i] << " ";
assert(ans1[i] != i);
}
cout << "\n";
for (int i = 1; i <= n; i++) {
cout << ans2[i] << " ";
}
return 0;
}
