// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v; --u, --v;
adj[u].pb(v);
adj[v].pb(u);
}
vi sub(N); function<void(int, int)> gen = [&](int u, int p) {
sub[u] = 1;
for(auto& v : adj[u]) if (v != p) {
gen(v, u); sub[u] += sub[v];
}
};
function<int(int, int)> find = [&](int u, int p) {
for(auto& v : adj[u]) if (v != p) {
if (2 * sub[v] >= N) return find(v, u);
}
return u;
};
gen(0, -1); int R = find(0, -1);
// cout << R << endl;
ll lans = 0, gans = 0;
vi L(N), G(N); iota(begin(L), end(L), 0);
vi ord;
function<int(int, int)> answer = [&](int u, int p) {
ord.pb(u); sub[u] = 1;
vi chd = {u};
for(auto& v : adj[u]) if (v != p) {
int r = answer(v, u);
sub[u] += sub[v];
gans += 2 * sub[v];
if (r != -1) chd.pb(r);
}
if (sz(chd) == 1) {
lans += 2;
return chd[0];
}
for(int i = 0; i < sz(chd); i++) {
int j = (i + 1) % sz(chd);
L[chd[j]] = chd[i];
}
return -1;
};
int r = answer(R, -1);
if (r != -1) {
for(auto& v : adj[R]) {
swap(L[R], L[v]);
break;
}
}
int mx = 0;
for(auto& v : adj[R]) mx = max(mx, sub[v]);
for(int x = 0; x < N; x++) {
int y = (x + mx) % N;
G[ord[y]] = ord[x];
}
cout << lans << " " << gans << nl;
for(auto& x : L) cout << x + 1 << " ";
cout << nl;
for(auto& x : G) cout << x + 1 << " ";
cout << nl;
exit(0-0);
}
