#include <bits/stdc++.h>
// #define int long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 7;
const int MOD = 998244353;
const int INF = (int)1e9 + 7;
int n, m, t, flag, k, u, v, w, ans, ans2, tmp, tmp2, tmp3, tmp4;
int arr[MAXN], arr2[MAXN], par[MAXN], h[MAXN], sz[MAXN], cent;
int arr3[MAXN], arr4[MAXN];
vector<int> adj[MAXN];
bool DFS(int v, int p=-1) {
bool res = 0;
for (int u:adj[v]) {
if (u != p) res |= DFS(u, v);
}
if (res) return 0;
if (v != 1) {
swap(arr[v], arr[p]);
ans++;
return 1;
}
swap(arr[1], arr[adj[1][0]]);
ans++;
return 0;
}
void DFSsz(int v, int p=-1) {
sz[v] = 1;
for (int u:adj[v]) {
if (u == p) continue;
DFSsz(u, v);
sz[v] += sz[u];
}
}
int centroid(int tot, int v, int p=-1) {
for (int u:adj[v]) {
if (u != p && 2*sz[u] > tot) {
return centroid(tot, u, v);
}
}
return v;
}
vector<int> vec, vec2;
vector<pii> love;
pii tof;
void DFS2(int v, int p=-1) {
vec2.pb(v);
for (int u:adj[v]) {
if (u == p || u == cent) continue;
DFS2(u, v);
}
}
void solve() {
vec.pb(cent);
tmp4 = 1;
for (int u:adj[cent]) {
love.pb(mp(sz[u], u));
}
sort(all(love), greater<pii>());
for (auto cur:love) {
u = cur.S;
// vec2.clear();
DFS2(u);
reverse(all(vec));
tmp4 += vec2.size();
while (vec.size() && vec2.size()) {
if (tof.F == -1) tof = mp(vec.back(), vec2.back());
swap(arr3[vec.back()], arr3[vec2.back()]);
vec2.pop_back();
vec.pop_back();
}
while (vec2.size()) {
vec.pb(vec2.back());
vec2.pop_back();
}
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
tof.F = -1;
cin >> n;
for (int i=1; i<n; i++) {
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
// Min
for (int i=1; i<=n; i++) arr[i] = i;
DFS(1);
for (int i=1; i<=n; i++) arr2[arr[i]] = i;
// Max
DFSsz(1);
cent = centroid(n, 1);
DFSsz(cent);
for (int i=1; i<=n; i++) arr3[i] = i;
solve();
// cout << "!" << cent << endl;
for (int i=1; i<=n; i++) if (i != cent) ans2 += sz[i];
if (tmp4%2) {
u = vec.back();
v = tof.F;
w = tof.S;
swap(arr3[v], arr3[w]);
arr3[u] = w;
arr3[v] = u;
arr3[w] = v;
}
cout << 2*ans << " " << 2*ans2 << endl;
for (int i=1; i<=n; i++) cout << arr2[i] << " ";
cout << endl;
for (int i=1; i<=n; i++) arr4[arr3[i]] = i;
for (int i=1; i<=n; i++) cout << arr4[i] << " ";
cout << endl;
return 0;
}
