#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) int(x.size())
const int MXN = 1e5+5;
int n, h[MXN], par[MXN], ord[MXN], sz[MXN], ans_mn, p_mn[MXN], p_mx[MXN];
ll ans_mx;
bool mark[MXN], vis[MXN];
vector<int> g[MXN], G[MXN];
void dfs1(int v) {
sz[v] = 1;
for(int u : g[v])
if(u!=par[v]) {
par[u] = v;
h[u] = h[v]+1;
dfs1(u);
sz[v] += sz[u];
}
}
vector<int> vec;
void dfs2(int v) {
vec.push_back(v);
vis[v] = 1;
for(int u : G[v])
if(!vis[u])
dfs2(u);
}
int centroid(int v) {
for(int u : g[v])
if(u!=par[v] && sz[u]+sz[u]>n)
return centroid(u);
return v;
}
void dfs3(int v, int p=0) {
vec.push_back(v);
for(int u : g[v])
if(u!=p)
dfs3(u, v);
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for(int i=0,u,v; i<n-1; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1);
iota(ord+1, ord+n+1, 1);
sort(ord+1, ord+n+1, [&](int u, int v) {
return h[u]>h[v];
});
for(int i=1; i<=n; i++) {
int v = ord[i];
if(mark[v]) continue;
ans_mn += 2;
if(h[v]==0) {
G[v].push_back(g[v][0]);
G[g[v][0]].push_back(v);
}
else {
G[v].push_back(par[v]);
G[par[v]].push_back(v);
mark[par[v]] = 1;
}
}
for(int i=1; i<=n; i++) if(!vis[i]) {
dfs2(i);
for(int j=0; j<SZ(vec); j++)
p_mn[vec[j]] = vec[(j+1)%SZ(vec)];
}
for(int i=1; i<=n; i++) ans_mx += 2*min(sz[i], n-sz[i]);
vec.clear();
dfs3(centroid(1));
if(n&1) {
p_mx[vec[0]] = vec[1];
p_mx[vec[1]] = vec[1+n/2];
p_mx[vec[1+n/2]] = vec[0];
for(int i=2; i+n/2<n; i++)
p_mx[vec[i]] = vec[i+n/2],
p_mx[vec[i+n/2]] = vec[i];
}
else {
for(int i=0; i+n/2<n; i++)
p_mx[vec[i]] = vec[i+n/2],
p_mx[vec[i+n/2]] = vec[i];
}
cout << ans_mn << ' ' << ans_mx << '\n';
for(int i=1; i<=n; i++) cout << 1 << ' ';
cout << '\n';
for(int i=1; i<=n; i++) cout << p_mx[i] << ' ';
cout << '\n';
return 0;
}
