#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define int long long
vector<vector<int>> graph;
vector<int> subsize;
vector<int> subtree;
int cent = -1;
int ds = 0;
int n;
vector<int> match;
vector<int> matched;
int dds = 0;
void dp(int i, int p)
{
vector<int> nodes;
for (int ele:graph[i])
{
if (ele == p) continue;
dp(ele, i);
if (matched[ele]==0) nodes.push_back(ele);
}
if (nodes.size()==0) return;
dds += nodes.size()*2;
match[i] = nodes[0];
for (int j = 0; j < nodes.size()-1; j++)
{
match[nodes[j]] = nodes[j+1];
}
match[nodes.back()] = i;
matched[i] = 1;
}
void dfs(int i, int p)
{
int sum = 0;
bool b = 1;
for (int ele:graph[i])
{
if (ele == p) continue;
dfs(ele, i);
if (subsize[ele]*2>n) b = 0;
subsize[i] += subsize[ele];
sum += subsize[ele];
}
sum = n-sum-1;
if (sum*2>n) b=0;
if (b) cent = i;
subsize[i]++;
}
void dist(int i, int p, int d)
{
for (int ele:graph[i])
{
if (ele == p) continue;
dist(ele, i, d+1);
}
ds += d;
}
void sub(int i, int p)
{
subtree.push_back(i);
for (int ele:graph[i])
{
if (ele == p) continue;
sub(ele, i);
}
}
bool comp(vector<int> &a, vector<int> &b)
{
if (a.size() > b.size()) return 1;
else return 0;
}
int32_t main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
graph.assign(n, vector<int>());
subsize.assign(n, 0);
match.assign(n, 0);
matched.assign(n, 0);
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
a--; b--;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(0, -1);
dp(cent, -1);
int mx = -1;
dist(cent, -1, 0);
mx = ds*2;
vector<vector<int>> subs;
for (int i = 0; i < graph[cent].size(); i++)
{
sub(graph[cent][i], cent);
subs.push_back(subtree);
subtree.clear();
}
subs.push_back(vector<int>(1, cent));
sort(subs.begin(), subs.end(), comp);
cout << dds << " " << mx << endl;
vector<int> left;
vector<int> ini;
vector<int> part(n, 0);
for (auto ele:subs)
{
for (int e:ele)
{
ini.push_back(e);
left.push_back(e);
}
}
for (int i = 0; i < subs[0].size(); i++)
{
part[ini[i]] = left.back();
left.pop_back();
}
int i = subs[0].size();
for (int ele:left)
{
part[ini[i]] = ele;
i++;
}
for (int i = 0; i <n; i++) cout << match[i]+1 << " ";
cout << endl;
for (int ele:part) cout << ele+1 << " ";
}
