#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int MOD = 998244353;
struct LCA{
vector<vector<int>> dp;
vector<int> depths;
void DFS(int x, vector<vector<int>>& adj, int p){
dp[x][0] = p;
for(auto node : adj[x]){
if(node != p){
depths[node] = depths[x] + 1;
DFS(node, adj, x);
}
}
}
void build(vector<vector<int>>& adj){
int n = adj.size();
dp.assign(n, vector<int>(20, 0)); depths.resize(n);
depths[0] = 0;
DFS(0, adj, -1);
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++){
if(dp[j][i - 1] == -1) {dp[j][i] = -1; continue;}
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}
}
int kth(int x, int d){
for(int k = 19; k >= 0; k--){
if((1 << k) <= d){
x = dp[x][k];
d -= (1 << k);
}
}
return x;
}
int lca(int a, int b){
if(depths[b] > depths[a]) b = kth(b, depths[b] - depths[a]);
else if(depths[a] > depths[b]) a = kth(a, depths[a] - depths[b]);
if(a == b) return a;
int anc = -1;
for(int k = 19; k >= 0; k--){
if(dp[a][k] == dp[b][k]){
anc = max(0, dp[a][k]);
}else{
a = dp[a][k];
b = dp[b][k];
}
}
return anc;
}
int dist(int a, int b){
return depths[a] + depths[b] - 2 * depths[lca(a, b)];
}
};
struct maximum{
int centr = -1;
int find_centroid(int x, vector<vector<int>>& adj, int p){
if(centr != -1) return -1;
int n = adj.size();
int subtree = 1;
bool good = 1;
for(int node : adj[x]){
if(node == p) continue;
int sub = find_centroid(node, adj, x);
if(centr != -1) return -1;
subtree += sub;
if(sub > n / 2) good = 0;
}
if(good == 1 && n - subtree <= n / 2){
centr = x;
return -1;
}else return subtree;
}
void DFS(int x, vector<vector<int>>& adj, vector<int>& euler, int p){
euler.push_back(x);
for(int node : adj[x]){
if(node == p) continue;
DFS(node, adj, euler, x);
}
}
pair<ll, vector<int>> solve(vector<vector<int>> adj){
int n = adj.size();
find_centroid(0, adj, -1);
vector<int> euler;
DFS(centr, adj, euler, -1);
ll ans = 0;
LCA lca; lca.build(adj);
vector<int> v(n);
for(int i = 0; i < n; i++){
ans += lca.dist(euler[i], euler[(i + n / 2) % n]);
v[euler[i]] = euler[(i + n / 2) % n];
}
return {ans, v};
}
};
struct minimum{
vector<int> v;
int ans = 0;
bool DFS(int x, vector<vector<int>>& adj, int p){
vector<int> odd;
for(int node : adj[x]){
if(node == p) continue;
bool rep = DFS(node, adj, x);
if(rep) odd.push_back(node);
}
if(odd.size() == 0){
if(x == 0){
int node = adj[x][0];
if(v[v[node]] == node){
v[x] = v[node];
v[node] = x;
ans += 2;
}else{
int node1 = v[node];
int node2 = v[v[node]];
v[node1] = node2;
v[node2] = node1;
v[x] = node;
v[node] = x;
ans += 2;
}
}else return 1;
}else{
if(((int)odd.size()) % 2 == 1){
for(int i = 1; i < (int)odd.size() - 1; i += 2){
v[odd[i]] = odd[i + 1];
v[odd[i + 1]] = odd[i];
ans += 4;
}
v[x] = odd[0];
v[odd[0]] = x;
ans += 2;
}else{
for(int i = 2; i < (int)odd.size() - 1; i += 2){
v[odd[i]] = odd[i + 1];
v[odd[i + 1]] = odd[i];
ans += 4;
}
v[x] = odd[0];
v[odd[0]] = odd[1];
v[odd[1]] = x;
ans += 4;
}
}
return 0;
}
pair<int, vector<int>> solve(vector<vector<int>> adj){
int n = adj.size();
v.resize(n);
DFS(0, adj, -1);
return {ans, v};
}
};
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("inpt.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//int tt; cin >> tt;
int n; cin >> n;
vector<vector<int>> adj(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);
}
minimum men;
maximum mex;
pair<int, vector<int>> mn = men.solve(adj);
pair<ll, vector<int>> mx = mex.solve(adj);
cout << mn.first << " "<< mx.first << endl;
for(int x : mn.second) cout << x + 1 << " ";
cout << endl;
for(int x : mx.second) cout << x + 1 << " ";
cout << endl;
}
