#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
int n;
vector<int> graph[MaxN];
void Inp()
{
cin >> n;
for (int x = 1; x < n; x++)
{
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
}
int sz[MaxN];
void PreDFS(int u, int p)
{
sz[u] = 1;
for (int v : graph[u])
{
if (v != p)
{
PreDFS(v, u);
sz[u] += sz[v];
}
}
}
int FindCentroid(int u, int p)
{
for (int v : graph[u])
{
if (v != p && sz[v] > (n / 2))
{
return FindCentroid(v, u);
}
}
return u;
}
int curg;
int cnt[MaxN];
int group[MaxN];
int perm[MaxN];
int d[MaxN];
void DFS(int u, int p)
{
for (int v : graph[u])
{
if (v != p)
{
if (~p)
{
cnt[group[u]]++;
group[v] = group[u];
}
else
{
curg++;
cnt[curg]++;
group[v] = curg;
}
d[v] = d[u] + 1;
DFS(v, u);
}
}
}
int id[MaxN];
bool cmp(int a, int b)
{
if (cnt[group[a]] == cnt[group[b]])
{
return group[a] < group[b];
}
return cnt[group[a]] > cnt[group[b]];
}
void Exc()
{
PreDFS(1, -1);
int root = FindCentroid(1, -1);
DFS(root, -1);
long long res = 0;
for (int x = 1; x <= n; x++)
{
id[x] = x;
res += 2ll * d[x];
}
swap(id[n], id[root]);
sort(id + 1, id + n, cmp);
if (n & 1)
{
for (int x = 1; x + (n / 2) < n; x++)
{
perm[id[x]] = id[x + (n / 2)];
perm[id[x + (n / 2)]] = id[x];
}
perm[root] = root;
swap(perm[root], perm[id[n - 1]]);
}
else
{
for (int x = 1; x + (n / 2) <= n; x++)
{
perm[id[x]] = id[x + (n / 2)];
perm[id[x + (n / 2)]] = id[x];
}
}
cout << 0 << " " << res << "\n";
for (int x = 1; x <= n; x++)
{
cout << 0 << " ";
}
cout << "\n";
for (int x = 1; x <= n; x++)
{
cout << perm[x] << " ";
}
}
int main()
{
//freopen("A.INP", "r", stdin);
//freopen("A.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
