// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(i , l , r) for (int i=l; i<=r; i+=1)
#define arc(i , r , l) for (int i=r; i>=l; i-=1)
const int N = 1e5+7;
int n,Lo,Hi=0 , lo[N],hi[N],sz[N],so[N],k[N];
deque<pair<int,int>> q[N];
vector<int> e[N];
int root (int v)
{ return k[v]==v ? v:k[v]=root(k[v]); }
void Union (int u , int v , int d)
{
v=root(v); u=root(u);
if (so[v]<so[u]){ swap(v,u); }
k[u]=v;
deque<pair<int,int>> update;
vector<pair<int,int>> op;
loop(i,0,so[u]-1)
{
op.push_back({q[u].front().first,d});
op.push_back({q[v].front().first,d});
swap(hi[q[u].front().first],
hi[q[v].front().first]);
q[u].pop_front();
q[v].pop_front();
}
while (!q[v].empty())
{
update.push_back(q[v].front()); q[v].pop_front();
}
while (!op.empty())
{
update.push_back(op.back()); op.pop_back();
}
so[v] += so[u];
q[u].shrink_to_fit();
q[v]=update;
}
void brain_DFS (int v , int p , int d)
{
sz[v] = 1;
for (auto to : e[v])
{
if (to == p){ continue; }
brain_DFS(to,v,d+1); Union(v,to,d);
sz[v] += sz[to];
Hi += min(sz[to],n-sz[to]);
}
if (lo[v] == v)
{
if (v==p)
swap(lo[v],lo[e[v].front()]);
else
swap(lo[v],lo[p]);
Lo += 2;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
loop(i,1,n)
{
lo[i] = hi[i] = k[i] = i;
so[i]=1; q[i].push_back({i,n+5});
}
loop(i,1,n-1)
{
int u,v; cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
brain_DFS(1,1,0);
cout << Lo << " " << 2*Hi << '\n';
loop(i,1,n){ cout << lo[i] << " "; }
cout << '\n';
loop(i,1,n){ cout << hi[i] << " "; }
cout << '\n';
}
