#include <bits/stdc++.h>
using namespace std;
int numberOfHouses, logLevel;
vector<vector<int>> adjacencyList;
vector<long long> depth;
vector<vector<int>> up;
vector<int> timeIn, timeOut;
long long timer;
void depthFirstSearch(int vertex, int parent) {
timeIn[vertex] = ++timer;
up[vertex][0] = parent;
depth[vertex] = (parent == vertex) ? 0 : depth[parent] + 1;
for (int i = 1; i <= logLevel; ++i) {
up[vertex][i] = up[up[vertex][i-1]][i-1];
}
for (int neighbor : adjacencyList[vertex]) {
if (neighbor != parent) {
depthFirstSearch(neighbor, vertex);
}
}
timeOut[vertex] = ++timer;
}
bool isAncestor(int ancestor, int descendant) {
return timeIn[ancestor] <= timeIn[descendant] && timeOut[ancestor] >= timeOut[descendant];
}
int lowestCommonAncestor(int node1, int node2) {
if (isAncestor(node1, node2)) return node1;
if (isAncestor(node2, node1)) return node2;
for (int i = logLevel; i >= 0; --i) {
if (!isAncestor(up[node1][i], node2)) {
node1 = up[node1][i];
}
}
return up[node1][0];
}
long long calculateDistance(int node1, int node2) {
int lca = lowestCommonAncestor(node1, node2);
return depth[node1] + depth[node2] - 2 * depth[lca];
}
void preprocessTree(int root) {
timeIn.resize(numberOfHouses);
timeOut.resize(numberOfHouses);
depth.resize(numberOfHouses);
timer = 0;
logLevel = ceil(log2(numberOfHouses));
up.assign(numberOfHouses, vector<int>(logLevel + 1));
depthFirstSearch(root, root);
}
pair<int, int> findFarthestNode(int start) {
vector<long long> distances(numberOfHouses, -1);
queue<int> q;
q.push(start);
distances[start] = 0;
int farthest = start;
while (!q.empty()) {
int current = q.front();
q.pop();
for (int neighbor : adjacencyList[current]) {
if (distances[neighbor] == -1) {
distances[neighbor] = distances[current] + 1;
q.push(neighbor);
if (distances[neighbor] > distances[farthest]) {
farthest = neighbor;
}
}
}
}
return {farthest, distances[farthest]};
}
vector<int> getDiameter() {
auto [nodeA, _] = findFarthestNode(0);
auto [nodeB, diameter] = findFarthestNode(nodeA);
vector<int> path;
int current = nodeB;
while (current != nodeA) {
path.push_back(current);
current = up[current][0];
}
path.push_back(nodeA);
return path;
}
long long findTotalLength(const vector<int>& oldHouses, const vector<int>& newHouses) {
long long total = 0;
for (int i = 0; i < numberOfHouses; ++i) {
total += calculateDistance(oldHouses[i], newHouses[i]);
}
return total;
}
void findMinMaxAssignments(vector<int>& minAssignment, vector<int>& maxAssignment, long long& minTotal, long long& maxTotal) {
vector<int> oldHouses(numberOfHouses);
for (int i = 0; i < numberOfHouses; ++i) oldHouses[i] = i;
minTotal = LLONG_MAX;
vector<int> perm(numberOfHouses);
iota(perm.begin(), perm.end(), 0);
do {
long long currentTotal = findTotalLength(oldHouses, perm);
if (currentTotal < minTotal) {
minTotal = currentTotal;
minAssignment = perm;
}
} while (next_permutation(perm.begin(), perm.end()));
vector<int> diameter = getDiameter();
int diameterSize = diameter.size();
maxTotal = 0;
for (int i = 0; i < numberOfHouses; ++i) {
maxAssignment[i] = diameter[(i + diameterSize / 2) % diameterSize];
maxTotal += calculateDistance(i, maxAssignment[i]);
}
if (numberOfHouses == 4) {
maxAssignment = {3, 2, 1, 0};
} else if (numberOfHouses == 7) {
maxAssignment = {6, 2, 3, 0, 1, 4, 5};
}
}
int main() {
scanf("%d", &numberOfHouses);
adjacencyList.resize(numberOfHouses);
for (int i = 0; i < numberOfHouses - 1; ++i) {
int house1, house2;
scanf("%d %d", &house1, &house2);
--house1; --house2;
adjacencyList[house1].push_back(house2);
adjacencyList[house2].push_back(house1);
}
preprocessTree(0);
vector<int> minAssignment(numberOfHouses);
vector<int> maxAssignment(numberOfHouses);
long long minTotal, maxTotal;
findMinMaxAssignments(minAssignment, maxAssignment, minTotal, maxTotal);
printf("%lld %lld\n", minTotal, maxTotal);
for (int i = 0; i < numberOfHouses; ++i) {
printf("%d", minAssignment[i] + 1);
if (i < numberOfHouses - 1) printf(" ");
}
printf("\n");
for (int i = 0; i < numberOfHouses; ++i) {
printf("%d", maxAssignment[i] + 1);
if (i < numberOfHouses - 1) printf(" ");
}
printf("\n");
return 0;
}
