#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 10 + 1;
vector <int> adj[maxn];
int dis[maxn][maxn];
void dfs(int s, int p, int d, int og) {
dis[og][s] = d;
for (auto i : adj[s]) {
if (i == p)
continue;
dfs(i, s, d+1, og);
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 0; i < n; i++)
dfs(i, i, 0, i);
vector <int> nums(n);
for (int i = 0; i < n; i++)
nums[i] = i;
int min_path = 1e9, max_path = 0;
vector <int> min_path_nodes, max_path_nodes;
do {
int ans = 0;
for (int i = 0; i < n; i++) {
if (i == nums[i]) {
ans = 1e9;
break;
}
ans += dis[i][nums[i]];
}
if (ans == 1e9)
continue;
if (min_path > ans) {
min_path = ans;
min_path_nodes = nums;
}
if (max_path < ans) {
max_path = ans;
max_path_nodes = nums;
}
} while(next_permutation(nums.begin(), nums.end()));
cout << min_path << ' ' << max_path << '\n';
for (auto i : min_path_nodes)
cout << i+1 << ' ';
cout << '\n';
for (auto i : max_path_nodes)
cout << i+1 << ' ';
cout << '\n';
}
