#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
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 x : graph[u])
{
if (x != p)
{
PreDFS(x, u);
sz[u] += sz[x];
}
}
}
int FindCentroid(int u, int p)
{
for (int x : graph[u])
{
if (x != p && sz[x] > (n / 2))
{
return FindCentroid(x, u);
}
}
return u;
}
int cur;
int group[MaxN];
int cnt[MaxN];
int permmx[MaxN];
int d[MaxN];
void DFSmx(int u, int p)
{
for (int v : graph[u])
{
if (v != p)
{
if (p == -1)
{
cur++;
cnt[cur]++;
group[v] = cur;
}
else
{
cnt[group[u]]++;
group[v] = group[u];
}
d[v] = d[u] + 1;
DFSmx(v, u);
}
}
}
int id[MaxN];
bool cmp(int a, int b)
{
return cnt[group[a]] > cnt[group[b]];
}
struct Best
{
int r0, r1, r2;
Best(int _r0, int _r1, int _r2)
{
r0 = _r0;
r1 = _r1;
r2 = _r2;
}
};
int permin[MaxN];
int F[3][MaxN];
vector<Best> track[MaxN];
bool haschild[MaxN];
void DFSmi(int u, int p)
{
F[0][u] = inf;
F[1][u] = inf;
F[2][u] = 0;
for (int x : graph[u])
{
if (x != p)
{
DFSmi(x, u);
haschild[u] = true;
int pre0 = F[0][u], pre1 = F[1][u], pre2 = F[2][u];
Best tracking = Best(0, 0, 2);
F[0][u] = min(min(pre0 + F[0][x], pre1 + F[1][x] + 2), inf);
F[1][u] = min(min(pre0 + F[1][x] + 2, min(pre1 + F[0][x], pre2 + F[1][x] + 2)), inf);
F[2][u] = min(pre2 + F[0][x], inf);
if (pre0 + F[0][x] > pre1 + F[1][x] + 2)
{
tracking.r0 = 1;
}
if (F[1][u] == pre1 + F[0][x])
{
tracking.r1 = 1;
}
else if (F[1][u] == pre2 + F[1][x] + 2)
{
tracking.r1 = 2;
}
track[u].push_back(tracking);
}
}
Best tracking = Best(1, 0, 2);
int pre0 = F[0][u], pre1 = F[1][u], pre2 = F[2][u];
F[0][u] = pre1;
F[1][u] = min(pre0, pre2);
F[2][u] = pre2;
if (haschild[u])
{
if (F[0][u] > pre0)
{
F[0][u] = pre0;
tracking.r0 = 0;
}
if (F[0][u] > pre2 + 2)
{
F[0][u] = min(pre2 + 2, inf);
tracking.r0 = 2;
}
}
if (pre0 > pre2)
{
tracking.r1 = 2;
}
track[u].push_back(tracking);
}
int Track(int u, int par, int cur)
{
vector<int> sw;
int issw = 0;
if (cur == 0 && track[u].back().r0 != 1)
{
if (track[u].back().r0 == 0)
{
issw = 1;
cur = 0;
}
else
{
issw = 2;
cur = 2;
}
}
else
{
sw.push_back(u);
if (cur == 0)
{
cur = track[u].back().r0;
}
else
{
cur = track[u].back().r1;
}
}
track[u].pop_back();
int i = (int)track[u].size() - 1, p = -1;
for (int x = (int)graph[u].size() - 1; x >= 0; x--)
{
int v = graph[u][x];
if (v == par)
{
continue;
}
//cout << track[u][i].r0 << " " << track[u][i].r1 << " " << track[u][i].r2 << "\n";
bool t = false;
if (cur == 1)
{
t = (track[u][i].r1 == 0 || track[u][i].r1 == 2);
cur = track[u][i].r1;
}
else if (cur == 0)
{
t = (track[u][i].r0 == 1);
cur = track[u][i].r0;
}
i--;
if (t)
{
sw.push_back(Track(v, u, true));
if (issw == 1)
{
p = sw.back();
}
}
else
{
Track(v, u, false);
}
if (issw == 2)
{
p = v;
}
}
while ((int)sw.size() > 1)
{
int u = sw.back();
sw.pop_back();
int v = sw.back();
sw.pop_back();
permin[u] = v;
permin[v] = u;
}
if (issw == 1)
{
permin[u] = u;
swap(permin[u], permin[p]);
}
else if (issw == 2)
{
permin[u] = u;
swap(permin[u], permin[p]);
}
if (sw.empty())
{
return 0;
}
return sw.back();
}
void Exc()
{
PreDFS(1, -1);
int root = FindCentroid(1, -1);
DFSmx(root, -1);
long long resmx = 0;
for (int x = 1; x <= n; x++)
{
id[x] = x;
resmx += d[x] * 2;
}
swap(id[n], id[root]);
sort(id + 1, id + n, cmp);
if (n & 1)
{
for (int x = 1; x + (n / 2) < n; x++)
{
permmx[id[x]] = id[x + (n / 2)];
permmx[id[x + (n / 2)]] = id[x];
}
permmx[root] = root;
swap(permmx[root], permmx[id[n - 1]]);
}
else
{
for (int x = 1; x + (n / 2) <= n; x++)
{
permmx[id[x]] = id[x + (n / 2)];
permmx[id[x + (n / 2)]] = id[x];
}
}
DFSmi(1, -1);
Track(1, -1, 0);
cout << F[0][1] << " " << resmx << "\n";
for (int x = 1; x <= n; x++)
{
cout << permin[x] << " ";
}
cout << "\n";
for (int x = 1; x <= n; x++)
{
cout << permmx[x] << " ";
}
}
int main()
{
//freopen("VILLAGE.INP", "r", stdin);
//freopen("VILLAGE.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;
}
