#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 100010;
int n, c, cnt;
vector<int> g[MAXN], nodes;
int minans, maxans;
int par[MAXN];
int sz[MAXN];
int vis[MAXN];
int pos[MAXN], dep[MAXN];
int mnc[MAXN], mxc[MAXN];
int group[MAXN];
vector<int> cent;
void getsz(int x, int fa) {
sz[x] = 1;
par[x] = fa;
dep[x] = dep[fa] + 1;
for (auto i: g[x]) {
if (i == fa)
continue;
getsz(i, x);
sz[x] += sz[i];
}
}
int centroid(int x, int fa) {
for (auto i: g[x]) {
if (i == fa)
continue;
if (sz[i] * 2 > n)
return centroid(i, x);
}
return x;
}
void dfs(int x, int fa, int branch) {
group[x] = branch;
for (auto i: g[x]) {
if (i == fa)
continue;
if (x == c)
dfs(i, x, ++cnt);
else
dfs(i, x, branch);
}
}
signed main() {
fast;
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
getsz(1, 1);
c = centroid(1, 1);
// Minimum
for (int i = 1; i <= n; ++i) {
nodes.pb(i);
pos[i] = i;
}
sort(nodes.begin(), nodes.end(), [](int a, int b) {
return sz[a] < sz[b];
});
for (auto i: nodes) {
if (vis[i])
continue;
bool ok = false;
for (auto j: g[i]) {
if (vis[j])
continue;
minans += 2, vis[j] = 1, ok = true;
swap(pos[i], pos[j]);
break;
}
if (!ok) {
minans += 2;
swap(pos[i], pos[par[i]]);
if (i == par[i])
swap(pos[i], pos[g[i].back()]);
}
vis[i] = 1;
}
for (int i = 1; i <= n; ++i)
mnc[pos[i]] = i;
// Maximum
getsz(c, c);
for (int i = 1; i <= n; ++i) {
for (auto j: g[i]) {
int hi = i, lo = j;
if (dep[i] > dep[j])
swap(lo, hi);
maxans += min(n - sz[lo] + 1, sz[lo]);
}
}
dfs(c, c, cnt );
sort(nodes.begin(), nodes.end(), [](int a, int b) {
return group[a] < group[b];
});
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; ++i)
pos[i] = i;
int j = 1;
for (int i = 1; i < n; ++i) {
if (vis[nodes[i]] || vis[nodes[j]])
continue;
j = max(j, i);
while (group[nodes[i]] == group[nodes[j]])
++j;
if (j >= n)
break;
swap(pos[nodes[i]], pos[nodes[j]]);
vis[nodes[i]] = 1, vis[nodes[j]] = 1;
++j;
}
if (n % 2)
swap(pos[nodes.back()], pos[c]);
else {
for (int i = 1; i < n; ++i) {
if (!vis[nodes[i]]) {
swap(pos[c], pos[nodes[i]]);
}
}
}
for (int i = 1; i <= n; ++i)
mxc[pos[i]] = i;
cout << minans << ' ' << maxans << '\n';
for (int i = 1; i <= n; ++i)
cout << mnc[i] << ' ';
cout << '\n';
for (int i = 1; i <= n; ++i)
cout << mxc[i] << ' ';
return 0;
}
