// Village
// Alphine walley
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define REP(i, k) for(int i = 0 ; i < k ; i ++)
#define pb push_back
#define pii pair<int, int>
#define ll long long
#define sep ' '
#define F first
#define S second
const int N = 1e5+10;
int n;
vi adj[N];
bool used[N];
int ans[N];
int in[N];
int cnt = 0;
int sum = 0;
int sz[N];
vi V, V2;
int h[N];
bool good[N];
vi vert[N];
void gfs(int v, int p) {
V.pb(v);
for(int neigh: adj[v]) {
if (neigh != p) gfs(neigh, v);
}
}
void dfs(int v = 0, int p = -1) {
if (p != -1)
adj[v].erase(find(adj[v].begin(), adj[v].end(), p));
h[v] = (p == -1 ? 0 : h[p]+1);
sz[v]++;
vi vec;
for(int neigh: adj[v]) {
dfs(neigh, v);
sz[v] += sz[neigh];
if (!used[neigh]) vec.pb(neigh);
}
sum += min(sz[v], n-sz[v]);
if (!vec.empty()) {
used[v] = true;
ans[v] = vec.front();
for(int i = 0 ; i < vec.size()-1 ; i ++) ans[vec[i]] = vec[i+1];
ans[vec.back()] = v;
in[v] = vec.back();
cnt++;
} else {
if (v == 0) {
int u = adj[v].front();
ans[v] = u;
ans[in[u]] = v;
}
}
}
void solve() {
cin >> n;
vector<array<int, 2>> E;
REP(i, n-1) {
int a, b; cin >> a >> b; a--, b--;
adj[a].pb(b), adj[b].pb(a);
E.pb({a, b});
}
dfs();
cout << 2*(n-1) - 2*(cnt-1) << sep << 2*sum << '\n';
for(int i = 0 ; i < n ; i ++) cout << ans[i]+1 << sep;
cout << '\n';
fill(good, good+n, true);
REP(i, n) {
adj[i].clear();
}
for(auto [u, v]: E) adj[u].pb(v), adj[v].pb(u);
for(auto [u, v]: E) {
if (h[u] > h[v]) swap(u, v);
if (n%2 == 0 && sz[v]*2 == n) {
gfs(v, u);
swap(V, V2);
gfs(u, v);
for(int i = 0 ; i < n/2 ; i ++) {
ans[V[i]] = V2[i];
ans[V2[i]] = V[i];
}
for(int i = 0 ; i < n ; i ++) cout << ans[i]+1 << ' ';
cout << endl;
exit(0);
}
if (sz[v] <= n/2) {
good[v] = false;
} else good[u] = false;
}
int root = 0;
for(int i = 0 ; i < n ; i ++) {
if (good[i]) {
root = i;
break;
}
}
set<pii> st;
int x = 0;
for(int neigh: adj[root]) {
V.clear();
gfs(neigh, root);
st.insert({V.size(), x});
vert[x++] = V;
}
pii samp;
while(st.size() >= 2) {
auto [sz1, id1] = *st.rbegin();
st.erase(*st.rbegin());
auto [sz2, id2] = *st.rbegin();
st.erase(*st.rbegin());
ans[vert[id1].back()] = vert[id2].back();
ans[vert[id2].back()] = vert[id1].back();
samp = {vert[id1].back(), vert[id2].back()};
vert[id1].pop_back();
vert[id2].pop_back();
if (--sz1 > 0) {
st.insert({sz1, id1});
}
if (--sz2 > 0) {
st.insert({sz2, id2});
}
}
if (n&1) {
ans[root] = samp.F;
ans[samp.S] = root;
} else {
auto [_, id] = *st.rbegin();
ans[root] = vert[id].back();
ans[vert[id].back()] = root;
}
REP(i, n) cout << ans[i]+1 << ' ';
}
int32_t main() {
solve();
return 0;
}
