/*
Ben Watson
Quang Minh MasterDDDDD
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const string name = "test";
void solve();
signed main()
{
if (fopen((name + ".inp").c_str(), "r"))
{
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
// main program
const int maxn = 1e5 + 1;
const int maxbit = 17;
struct DSU
{
vector<int> par, sz;
int n;
DSU(int n) : n(n)
{
par.resize(n + 1, 0);
sz.resize(n + 1, 1);
for (int i = 1; i <= n; i++)
par[i] = i;
}
int find(int u) { return (u == par[u] ? u : par[u] = find(par[u])); }
int get(int u) { return sz[find(u)]; }
void merge(int u, int v)
{
u = find(u);
v = find(v);
if (u == v) return;
if (sz[u] > sz[v])
swap(u, v);
sz[v] += sz[u];
par[u] = v;
}
};
vector<int> adj[maxn], comp_mx[maxn], comp_mn[maxn];
int par[maxbit][maxn], d[maxn], sz[maxn];
int used[maxn], ans_mx[maxn], ans_mn[maxn];
DSU dsu(maxn);
int n, centroid;
void DFS_SZ(int u, int p = -1)
{
sz[u] = 1;
for (int v : adj[u])
{
if (v == p)
continue;
DFS_SZ(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int p = -1)
{
for (int v : adj[u])
{
if (v == p)
continue;
if (sz[v] > n / 2)
return find_centroid(v, u);
}
return u;
}
void DFS(int u, int p = -1)
{
sz[u] = 1;
for (int v : adj[u])
{
if (v == p)
continue;
par[0][v] = u;
d[v] = d[u] + 1;
for (int i = 1; i < maxbit; i++)
par[i][v] = par[i - 1][par[i - 1][v]];
DFS(v, u);
sz[u] += sz[v];
}
}
int LCA(int u, int v)
{
if (d[u] < d[v])
swap(u, v);
int k = d[u] - d[v];
for (int i = 0; i < maxbit; i++)
if (k >> i & 1)
u = par[i][u];
if (u == v) return u;
for (int i = maxbit - 1; i >= 0; i--)
if (par[i][u] != par[i][v])
{
u = par[i][u];
v = par[i][v];
}
return par[0][u];
}
int dist(int u, int v) { return d[u] + d[v] - 2 * d[LCA(u, v)]; }
void DFS_COMP(int u, int p, int top)
{
if (!used[u])
comp_mx[top].push_back(u);
for (int v : adj[u])
{
if (v == p)
continue;
DFS_COMP(v, u, top);
}
}
void DFS_MN(int u, int p = -1)
{
sz[u] = 1;
for (int v : adj[u])
{
if (v == p)
continue;
DFS_MN(v, u);
if (sz[v] == 0)
continue;
if (sz[v] == 1)
{
dsu.merge(u, v);
sz[u] += sz[v];
}
}
}
void solve()
{
cin >> n;
for (int i = 1; i < n; i++)
{
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
DFS_SZ(1);
centroid = find_centroid(1);
DFS(centroid);
if (n & 1)
{
vector<pair<int, int>> proc;
for (int v : adj[centroid])
proc.push_back({sz[v], v});
sort(proc.begin(), proc.end(), greater<pair<int, int>>());
int u = proc[0].second, v = proc[1].second;
used[u] = used[v] = used[centroid] = 1;
ans_mx[u] = v;
ans_mx[v] = centroid;
ans_mx[centroid] = u;
}
vector<int> proc;
for (int v : adj[centroid])
{
proc.push_back(v);
DFS_COMP(v, centroid, v);
}
priority_queue<pair<int, int>> pq;
if (!used[centroid])
{
pq.push({1, centroid});
comp_mx[centroid].push_back(centroid);
}
for (int x : proc)
pq.push({(int)comp_mx[x].size(), x});
while ((int)pq.size() > 1)
{
int x = pq.top().second;
pq.pop();
int y = pq.top().second;
pq.pop();
if (comp_mx[x].empty())
break;
int u = comp_mx[x].back(), v = comp_mx[y].back();
comp_mx[x].pop_back();
comp_mx[y].pop_back();
ans_mx[u] = v;
ans_mx[v] = u;
if (!comp_mx[x].empty())
pq.push({(int)comp_mx[x].size(), x});
if (!comp_mx[y].empty())
pq.push({(int)comp_mx[y].size(), y});
}
ll res_mx = 0;
for (int u = 1; u <= n; u++)
res_mx += dist(u, ans_mx[u]);
DFS_MN(1);
if (dsu.get(1) == 1)
dsu.merge(1, adj[1][0]);
for (int i = 1; i <= n; i++)
comp_mn[dsu.find(i)].push_back(i);
int res_mn = 0;
for (int i = 1; i <= n; i++)
{
int m = (int)comp_mn[i].size();
if (m == 0)
continue;
if (m == 2)
res_mn += 2;
else
res_mn += 2 + (m - 2) * 2;
for (int j = 1; j < m; j++)
ans_mn[comp_mn[i][j - 1]] = comp_mn[i][j];
ans_mn[comp_mn[i][m - 1]] = comp_mn[i][0];
}
cout << res_mn << ' ' << res_mx << '\n';
for (int i = 1; i <= n; i++)
cout << ans_mn[i] << ' ';
cout << '\n';
for (int i = 1; i <= n; i++)
cout << ans_mx[i] << ' ';
cout << '\n';
}
