#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
ll N;
vvi adj;
// Code for the mini length
vi dpP, dpN;
vi ans_mini;
ll miniCheck = 0;
void dfs_mini(ll v, ll p)
{
if (sz(adj[v]) == 1 && v != p)
{
// leaf
dpN[v] = 0;
dpP[v] = INT_MAX;
return;
}
for (ll u : adj[v])
if (u != p)
dfs_mini(u, v);
dpN[v] = 0;
for (ll u : adj[v])
if (u != p)
dpN[v] += min(dpP[u], dpN[u] + 2);
for (ll u : adj[v])
if (u != p)
{
ll tmp = dpN[v] - min(dpP[u], dpN[u] + 2) + min(dpP[u], dpN[u]) + 2;
dpP[v] = min(dpP[v], tmp);
}
}
void reconstruct_dpP(ll v, ll p);
void reconstruct_dpN(ll v, ll p, ll except);
void reconstruct_dpN(ll v, ll p, ll except = -1)
{
if (sz(adj[v]) == 1 && v != p)
return; // leaf
for (ll u : adj[v])
{
if (u == p)
continue;
if (u == except)
{
swap(ans_mini[v], ans_mini[u]);
miniCheck += 2;
if (dpP[u] < dpN[u])
reconstruct_dpP(u, v);
else
reconstruct_dpN(u, v);
}
else if (dpP[u] < dpN[u] + 2)
reconstruct_dpP(u, v);
else
{
swap(ans_mini[v], ans_mini[u]);
miniCheck += 2;
reconstruct_dpN(u, v);
}
}
}
void reconstruct_dpP(ll v, ll p)
{
if (sz(adj[v]) == 1 && v != p)
return; // leaf
ll w = -1;
for (ll u : adj[v])
if (u != p)
{
ll tmp = dpN[v] - min(dpP[u], dpN[u] + 2) + min(dpP[u], dpN[u]) + 2;
if (dpP[v] == tmp)
{
w = u;
break;
}
}
reconstruct_dpN(v, p, w);
}
// code for the maxi part
vi subsize, swapsRequired;
vvi contains;
vi ans_maxi;
void dfs_maxi(ll v, ll p)
{
subsize[v] = 1;
for (ll u : adj[v])
if (u != p)
{
dfs_maxi(u, v);
subsize[v] += subsize[u];
}
}
ll find_split(ll v)
{ // v must be root of the tree with respect to subsize
pii maxSub = {-1, -1};
for (ll u : adj[v])
maxSub = max(maxSub, {subsize[u], u});
if (maxSub.first <= N / 2)
return v;
subsize[v] = N - maxSub.first;
subsize[maxSub.second] = N;
return find_split(maxSub.second);
}
void collect(ll v, ll p)
{
contains[v].push_back(v);
for (ll u : adj[v])
if (u != p)
{
collect(u, v);
swapsRequired[v] += swapsRequired[u] + subsize[u];
if (v != p)
{
if (sz(contains[u]) > sz(contains[v]))
swap(contains[u], contains[v]);
while (!contains[u].empty())
contains[v].push_back(contains[u].back()), contains[u].pop_back();
}
}
}
void distribute(ll v)
{
vi places;
places.push_back(v);
for (ll u : adj[v])
places.push_back(u);
sort(all(places), [&](ll a, ll b)
{ return sz(contains[a]) > sz(contains[b]); });
queue<ll> todo;
for (ll u : places)
for (ll w : contains[u])
todo.push(w);
for (ll i = 0; i < sz(places); ++i)
for (ll u : contains[places[(i + 1) % sz(places)]])
ans_maxi[u] = todo.front(), todo.pop();
}
// main
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
adj.resize(N);
for (ll i = 0, a, b; i < N - 1; ++i)
{
cin >> a >> b, --a, --b;
adj[a].push_back(b), adj[b].push_back(a);
}
// mini
dpP.assign(N, INT_MAX), dpN.assign(N, INT_MAX);
dfs_mini(0, 0);
ans_mini.resize(N);
iota(all(ans_mini), 1);
reconstruct_dpP(0, 0);
// maxi
subsize.resize(N);
dfs_maxi(0, 0);
ll center = find_split(0);
contains.resize(N);
swapsRequired.assign(N, 0);
collect(center, center);
ans_maxi.resize(N);
distribute(center);
// ans
cout << dpP[0] << " ";
cout << 2 * swapsRequired[center] << endl;
assert(miniCheck == dpP[0]);
for (ll v : ans_mini)
cout << v << " ";
cout << endl;
for (ll v : ans_maxi)
cout << v + 1 << " ";
cout << endl;
return 0;
}
