#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 10;
int to[MAXN];
int sub[MAXN], used[MAXN];
vector<int> adj[MAXN];
int get_size(int v, int p){
sub[v] = 1;
for(auto u : adj[v]){
if(used[u] || u == p) continue;
sub[v] += get_size(u, v);
}
return sub[v];
}
int get_centroid(int v, int p, int sz){
for(auto u : adj[v]){
if(used[u] || u == p) continue;
if(sub[u] > sz / 2) return get_centroid(u, v, sz);
}
return v;
}
void get_vtx(int v, int p, vector<int> &vtx){
if(v != p) vtx.push_back(v);
for(auto u : adj[v]){
if(used[u] || u == p) continue;
get_vtx(u, v, vtx);
}
}
ll ans = 0;
void build(int v, int p){
int c = get_centroid(v, p, get_size(v, p));
used[c] = 1;
vector<pair<int, int>> to_add;
for(auto u : adj[c]){
if(used[u]) continue;
to_add.push_back({sub[u], u});
}
sort(to_add.begin(), to_add.end());
vector<int> vtx;
for(auto [s, u] : to_add) get_vtx(u, c, vtx);
int sz = (int) vtx.size();
ans += 2 * sz;
if(sz % 2 == 1){
for(int i=1; i<((sz + 1) / 2); i++) swap(to[vtx[i]], to[vtx[sz - i]]);
swap(to[vtx[0]], to[c]);
} else if(sz > 0){
for(int i=1; i<(sz / 2); i++) swap(to[vtx[i]], to[vtx[sz - 1 - i]]);
int x = to[vtx[0]], y = to[c], z = to[vtx[sz - 1]];
to[vtx[sz - 1]] = x;
to[vtx[0]] = y;
to[c] = z;
}
for(auto u : adj[c]){
if(used[u]) continue;
build(u, c);
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
for(int i=1; i<n; i++){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=n; i++) to[i] = i;
build(1, 1);
cout << "1 " << ans << "\n";
for(int i=1; i<=n; i++) cout << "1 ";
cout << "\n";
for(int i=1; i<=n; i++){
assert(to[i] != i);
cout << to[i] << " ";
}
cout << "\n";
return 0;
}
