#include <iostream>
#include <vector>
using i64 = int64_t;
const i64 INFINITY = __INT64_MAX__ / 1000;
std::pair<i64, i64> dfs(std::vector<std::vector<i64>> const &neighbours,
std::vector<std::pair<i64, i64>> &ann, i64 node,
i64 parent) {
auto child_count = neighbours[node].size() - (parent != -1);
if (child_count == 0) {
return ann[node] = {INFINITY, 2};
} else {
std::vector<std::pair<i64, i64>> results;
for (auto neighbour : neighbours[node]) {
if (neighbour == parent) continue;
results.push_back(dfs(neighbours, ann, neighbour, node));
}
// for k we have to move the root at least once
i64 best_choice = -1;
i64 why = INFINITY;
for (i64 i = 0; i < child_count; i++) {
if (results[i].second - results[i].first < why) {
best_choice = i;
why = results[i].second - results[i].first;
}
}
i64 k = 0;
for (i64 i = 0; i < child_count; i++) {
if (i == best_choice) {
k += results[i].second;
} else {
k += std::min(results[i].first, results[i].second);
}
}
i64 l = 2;
for (i64 i = 0; i < child_count; i++) {
l += std::min(results[i].first, results[i].second);
}
return ann[node] = {k, l};
}
}
std::pair<i64, i64> dfs_constructive(
std::vector<std::vector<i64>> const &neighbours,
std::vector<std::pair<i64, i64>> const &ann, i64 node, i64 parent, i64 mode,
std::vector<i64> &assignment) {
auto child_count = neighbours[node].size() - (parent != -1);
if (child_count == 0) {
if (mode & 0b01) {
return {node, node};
} else {
std::cerr << "SOMETHING IS WRONG\n";
return {-1, -1};
}
} else {
std::vector<i64> children;
for (auto neighbour : neighbours[node]) {
if (neighbour == parent) continue;
children.push_back(neighbour);
}
if (mode & 0b10 ||
(mode == 0b11 && ann[node].first <= ann[node].second)) {
// for k we have to move the root at least once
i64 best_choice = -1;
i64 why = INFINITY;
for (i64 i = 0; i < child_count; i++) {
if (ann[children[i]].second - ann[children[i]].first < why) {
best_choice = i;
why = ann[children[i]].second - ann[children[i]].first;
}
}
i64 moving = node;
for (i64 i = 0; i < child_count; i++) {
auto [to, from] = dfs_constructive(
neighbours, ann, children[i], node,
i == best_choice ? 0b01 : 0b11, assignment);
if (to != -1) {
assignment[moving] = to;
moving = from;
}
}
assignment[moving] = node; // ig
return {-1, -1};
} else {
i64 moving = node;
for (auto child : children) {
auto [to, from] = dfs_constructive(neighbours, ann, child, node,
0b11, assignment);
if (to != -1) {
assignment[moving] = to;
moving = from;
}
}
return {node, moving};
}
}
}
int main() {
i64 n;
std::cin >> n;
std::vector<std::vector<i64>> neighbours(n);
for (i64 i = 0; i < n - 1; i++) {
i64 a, b;
std::cin >> a >> b;
a--, b--;
neighbours[a].push_back(b);
neighbours[b].push_back(a);
}
std::vector<std::pair<i64, i64>> ann(n);
auto [k, l] = dfs(neighbours, ann, 0, -1);
std::cout << k << " 1\n";
std::vector<i64> assignment(n);
dfs_constructive(neighbours, ann, 0, -1, 0b10, assignment);
for (i64 x : assignment) {
std::cout << x + 1 << ' ';
}
std::cout << "\n";
for (i64 x : assignment) {
std::cout << x + 1 << ' ';
}
}
