#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
ll Sum(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a += b;
return a % MOD;
}
ll Mul(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a *= b;
return a % MOD;
}
ll Pow(ll a , ll b , ll MOD)
{
ll res = 1;
while(b)
{
if((b & 1))res = Mul(res , a , MOD);
a = Mul(a , a , MOD);
b >>= 1;
}
return res;
}
ll Min(ll a , ll b)
{
if(a > b)return b;
return a;
}
ll Max(ll a , ll b)
{
if(a > b)return a;
return b;
}
ll Ceil(ll a , ll b)
{
return a + (b-1) / b;
}
/////////////////////
//VALS
ll n;
const ll maxn = 2e5;
vector<ll> adj[maxn];
ll mx[maxn];
ll mn[maxn];
ll mx_ans, mn_ans;
ll sz[maxn];
ll centroid;
vector<ll> e;
/////////////////////
//FUNCTIONS
void dfs_mx_ans(ll u = 0, ll par = 0)
{
sz[u] = 1;
for(auto v : adj[u])
{
if(v == par)continue;
dfs_mx_ans(v, u);
sz[u] += sz[v];
}
ll x = Min(sz[u], n-sz[u]);
mx_ans += x*2;
}
void dfs_get_centroid(ll u = 0, ll par = 0)
{
bool flag = (n - sz[u] <= (n >> 1));
for(auto v : adj[u])
{
if(v == par)continue;
dfs_get_centroid(v, u);
if(sz[v] > (n >> 1))flag = 0;
}
if(flag)centroid = u;
}
void dfs_get_euler(ll u = centroid, ll par = centroid)
{
e.pb(u);
for(auto v : adj[u])
{
if(v == par)continue;
dfs_get_euler(v, u);
}
}
void dfs_mn(ll u = 0, ll par = 0)
{
for(auto v : adj[u])
{
if(v == par)continue;
dfs_mn(v, u);
}
if(mn[u] == u and u != 0)//swap with par
{
mn_ans += 2;
// ll tmp = mn[u];
// mn[u] = mn[par];
// mn[par] = tmp;
swap(mn[u], mn[par]);
}
if(mn[u] == u and u == 0)
{
mn_ans += 2;
// ll tmp = mn[u];
// mn[u] = mn[adj[u][0]];
// mn[adj[u][0]] = tmp;
swap(mn[u], mn[adj[u][0]]);
}
}
/////////////////////
//SOLVE
void solve()
{
cin >> n;
For(i,n-1)
{
ll u, v;
cin >> u >> v;
u--;v--;
adj[u].pb(v);
adj[v].pb(u);
}
// if(n == 2)
// {
// cout << 2 << " " << 2 << endl;
// cout << 2 << " " << 1 << endl;
// cout << 2 << " " << 1 << endl;
// return;
// }
//Max
dfs_mx_ans();
// debug(":L");
dfs_get_centroid();
// debug(":L");
dfs_get_euler();
// debug(":L");
if(n & 1)
{
mx[e[0]] = e[n/2]+1;
mx[e[n/2]] = e[n-1]+1;
mx[e[n-1]] = e[0]+1;
}
For(i,(n+1) / 2)
{
if(mx[e[i]])continue;
mx[e[i]] = e[i+n/2]+1;
mx[e[i+n/2]] = e[i]+1;
}
// cout << mx_ans << endl;
// For(i,n)cout << mx[i] + 1 << " ";
// cout << endl;
//Min
For(i,n)
mn[i] = i;
dfs_mn();
//print
cout << mn_ans << " " << mx_ans << endl;
For(i,n)cout << mn[i] + 1 << " ";
cout << endl;
For(i,n)cout << mx[i]/* + 1 */<< " ";
cout << endl;
}
/////////////////////
//MAIN
int main()
{
FAST;
ll t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
/////////////////////
/*
ZZZZZZZ A M M IIIIIII N N
Z A A M M M M I NN N
Z A A M M M M I N N N
Z AAAAAAA M M M I N N N
Z A A M M I N N N
Z A A M M I N NN
ZZZZZZZ A A M M IIIIIII N N TREE
*/
