#include <algorithm>
#include <ios>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
template <typename F>
class YCombinator {
private:
const F f = nullptr;
public:
explicit YCombinator(F&& f) : f(f) {}
template <typename... Ts>
decltype(auto) operator()(Ts&&... arguments) const {
return f(*this, std::forward<Ts>(arguments)...);
}
};
template <typename F>
YCombinator(F) -> YCombinator<F>;
auto solve() {
auto n = 0;
std::cin >> n;
auto adj = std::vector<std::vector<int>>(n);
for (auto i = 0; i < n - 1; ++i) {
auto a = 0;
auto b = 0;
std::cin >> a >> b;
--a;
--b;
adj[a].push_back(b);
adj[b].push_back(a);
}
auto idxs = std::vector<int>(n);
auto mn_len = 0;
auto mx_len = 0ll;
auto order = std::vector<int>();
auto szs = std::vector<int>(n, 1);
auto v = std::vector<int>(n);
order.reserve(n);
std::iota(std::begin(v), std::end(v), 0);
YCombinator(
[&](auto self, int node, int par) -> void {
order.push_back(node);
for (auto x : adj[node]) {
if (x != par) {
self(x, node);
mx_len += std::min(szs[x], n - szs[x]) * 2;
szs[node] += szs[x];
}
}
if (v[node] == node) {
std::swap(v[node], v[par != -1 ? par : adj[node][0]]);
mn_len += 2;
}
}
)(0, -1);
std::cout << mn_len << ' ' << mx_len << '\n';
for (auto i = 0; i < n; ++i) {
std::cout << v[i] + 1 << (i < n - 1 ? ' ' : '\n');
idxs[order[i]] = i;
}
for (auto i = 0; i < n; ++i) {
std::cout << order[(idxs[i] + n / 2) % n] + 1 << (i < n - 1 ? ' ' : '\n');
}
}
auto main() -> int {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
return 0;
}
