#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;
vector<pii> love;
pii tof;
void DFS2(int v, int p=-1) {
vec.pb(v);
for (int u:adj[v]) {
if (u == p) continue;
DFS2(u, v);
}
}
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);
DFS2(cent);
for (int i=0; i<n; i++) {
arr3[vec[i]] = vec[(i+(n/2))%n];
}
for (int i=1; i<=n; i++) if (i != cent) ans2 += sz[i];
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++) cout << arr3[i] << " ";
cout << endl;
return 0;
}
