#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int M = 100'001;
vector<vector<int>> g(M);
vector<vector<int>> dp(M, vector<int>(2));
vector<int> rep(M), deg(M), p(M), sel(M);
int Find(int v) {
return (rep[v]==v ? v : rep[v]=Find(rep[v]));
}
void Union(int a, int b){
rep[Find(a)] = Find(b);
}
void dfs(int v, int p) {
for(auto u : g[v]) if(u!=p) dfs(u,v);
dp[v][1] = dp[v][0] = 0;
for(auto u : g[v]) {
if(u==p) continue;
dp[v][0] += min(dp[u][0]+1, dp[u][1]);
dp[v][1] += dp[u][0]+1;
sel[v] = u;
}
for(auto u : g[v]) {
if(u==p) continue;
int val = dp[v][0]-min(dp[u][0]+1, dp[u][1]) + dp[u][0] + 1;
if(val < dp[v][1]) {
dp[v][1] = val;
sel[v] = u;
}
}
if(dp[v][1]==0) dp[v][1] = 1e9;
}
void add_edge(int a, int b) {
deg[a]++; deg[b]++;
Union(a,b);
}
void odzysk(int v, int p, int t) {
if(t==1) {
for(auto u : g[v]) {
if(u==p) continue;
if(dp[u][0]+1 < dp[u][1] || u==sel[v]) {
add_edge(u,v);
odzysk(u,v,0);
} else {
odzysk(u,v,1);
}
}
} else {
for(auto u : g[v]) {
if(u==p) continue;
if(dp[u][0]+1 < dp[u][1]) {
add_edge(u,v);
odzysk(u,v,0);
} else {
odzysk(u,v,1);
}
}
}
}
vector<int> parent(M), sajz(M), depth(M);
void depth_dfs(int v, int p) {
depth[v] = depth[p] + 1;
for(auto u : g[v]) if(u!=p) depth_dfs(u,v);
}
void sajz_dfs(int v, int p) {
parent[v] = p;
sajz[v] = 1;
for(auto u : g[v]) {
if(u==p) continue;
sajz_dfs(u, v);
sajz[v] += sajz[u];
}
}
int find_centroid(int v, int tree_size) {
for(auto u : g[v]) {
if(u == parent[v]) {
if(tree_size-sajz[v] > tree_size/2) return find_centroid(u, tree_size);
} else {
if(sajz[u] > tree_size/2) return find_centroid(u, tree_size);
}
}
return v;
}
vector<int> verts;
void get_verts(int v, int p) {
verts.push_back(v);
for(auto u : g[v]) if(u!=p) get_verts(u,v);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for(int i=0; i<M; ++i) rep[i] = i;
int n;
cin >> n;
for(int i=1; i<n; ++i) {
int a,b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
ll res=0;
vector<ll> p2(M,1);
sajz_dfs(1,0);
int ctr = find_centroid(1,n);
depth[0] = -1;
depth_dfs(ctr,0);
for(int i=1; i<=n; ++i) {
res += depth[i];
}
vector<vector<int>> V;
set<int> all;
for(int i=1; i<=n; ++i) all.insert(i);
for(auto u : g[ctr]) {
get_verts(u,ctr);
V.push_back(verts);
while(verts.size()) verts.pop_back();
}
auto cmp = [&](int i, int j) {
return V[i].size() > V[j].size();
};
set<pair<int, int>> akt;
for(int i=0; i<V.size(); ++i) akt.insert({V[i].size(), i});
while(all.size() > 3) {
int f = akt.rbegin()->second; akt.erase({V[f].size(), f});
int s = akt.rbegin()->second; akt.erase({V[s].size(), s});
int a = V[f].back(); V[f].pop_back();
int b = V[s].back(); V[s].pop_back();
p2[a] = b;
p2[b] = a;
all.erase(a); all.erase(b);
if(V[f].size()) akt.insert({V[f].size(), f});
if(V[s].size()) akt.insert({V[s].size(), s});
}
int x1 = *all.begin(); all.erase(x1);
int x2 = *all.begin(); all.erase(x2);
if(all.empty()) {
p2[x1] = x2;
p2[x2] = x1;
} else {
int x3 = *all.begin(); all.erase(x3);
p2[x1] = x2;
p2[x2] = x3;
p2[x3] = x1;
}
dfs(1,0);
odzysk(1,0,1);
vector<vector<int>> S(n+1);
for(int i=1; i<=n; ++i) {
S[rep[i]].push_back(i);
}
for(int i=1; i<=n; ++i) {
if(S[i].empty()) continue;
int c=0;
vector<int> vec;
for(auto x : S[i]) {
if(deg[x]==1) vec.push_back(x);
else c=x;
}
if(c==0) {
c=vec.back(); vec.pop_back();
}
// cout << c << ": "; for(auto x : vec) cout << x << " "; cout << "\n";
while(vec.size() > 2) {
int a = vec.back(); vec.pop_back();
int b = vec.back(); vec.pop_back();
p[a] = b;
p[b] = a;
}
int a = vec.back(); vec.pop_back();
if(vec.empty()) {
p[a] = c;
p[c] = a;
continue;
}
int b = vec.back(); vec.pop_back();
p[a] = b;
p[b] = c;
p[c] = a;
}
cout << 2*dp[1][1] << " " << 2*res << "\n";
for(int i=1; i<=n; ++i) cout << p[i] << " "; cout << '\n';
for(int i=1; i<=n; ++i) cout << p2[i] << " "; cout << "\n";
return 0;
}
