#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define pb push_back
#define F first
#define S second
//#define int long long
const int maxn = 1e6 + 10;
const int LOG = 21;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
ll n, ret, ans, mn[maxn], sub[maxn], h[maxn], st[maxn];
vector<ll> G[maxn], res;
int clo = 0;
int dfs_sz(int v, int p) {
sub[v] = 1;
for (int u : G[v]) {
if (u == p) continue;
sub[v] += dfs_sz(u, v);
}
return sub[v];
}
int centroid(int v, int sz, int p) {
for (int u : G[v]) {
if (u == p) continue;
if (sz < sub[u] * 2)
return centroid(u, sz, v);
}
return v;
}
void dfs(int v, int p) {
st[v] = clo++;
res.pb(v);
for (int u : G[v]) {
if (u == p) continue;
h[u] = h[v] + 1;
ret += h[u];
dfs(u, v);
}
}
void dfs2(int v = 1, int p = 0){
mn[v] = v;
for (int u : G[v]) {
if (u == p) continue;
dfs2(u, v);
}
if (mn[v] == v) {
ans += 2;
if (p > 0) {
swap(mn[v], mn[p]);
}
else {
swap(mn[v], mn[G[v][0]]);
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int v, u;
cin >> v >> u;
G[v].pb(u);
G[u].pb(v);
}
int cen = centroid(1, dfs_sz(1, 0), 0);
dfs(cen, 0);
dfs2();
cout << ans << ' ' << ret * 2 << '\n';
for (int i = 1; i <= n; i++)
cout << mn[i] << ' ';
cout << '\n';
for (int i = 1; i <= n; i++) {
cout << res[(st[i] + n / 2) % n] << ' ';
}
cout << '\n';
}
