#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
int N;
vector<ii> edges;
vi adj[100005];
pair<int, vi> minimumans;
void bruteforce() {
vector<vi> dist(N, vi(N, 1e9));
for (int i = 0; i < N; i++) { // starting node
queue<int> q;
dist[i][i] = 0;
q.push(i);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int j : adj[x]) {
if (dist[i][j] == 1e9) {
dist[i][j] = dist[i][x] + 1;
q.push(j);
}
}
}
}
/*
cout<<"dist: "<<endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
*/
vi perm(N);
for (int i = 0; i < N; i++) {
perm[i] = i;
}
int minimum = 1e9;
vi minans;
int maximum = 0;
vi maxans;
int count = 0;
do {
bool can = true;
for (int i = 0; i < N; i++) {
if (perm[i] == i)
can = false;
}
if (!can)
continue;
count++;
int total = 0;
for (int i = 0; i < N; i++) {
total += dist[i][perm[i]];
}
if (total < minimum) {
minimum = total;
minans = perm;
}
if (total > maximum) {
maximum = total;
maxans = perm;
}
} while (next_permutation(perm.begin(), perm.begin() + N));
// cout<<"count: "<<count<<endl;
/*
cout<<minimum<<" "<<maximum<<endl;
for (int i = 0; i < N; i++) {
cout<<(minans[i] + 1)<<" ";
}
cout<<endl;
for (int i = 0; i < N; i++) {
cout<<(maxans[i] + 1)<<" ";
}
cout<<endl;
*/
minimumans.fi = minimum;
minimumans.se = minans;
}
int subtree_size[100005];
bool vis[100005];
void dfs(int n) {
vis[n] = true;
subtree_size[n] = 1;
for (int i : adj[n]) {
if (!vis[i]) {
dfs(i);
subtree_size[n] += subtree_size[i];
}
}
}
bool vis2[100005];
int dfs2(int n) {
// cout<<"at "<<n<<endl;
vis2[n] = true;
bool works = true;
for (int i : adj[n]) {
if (!vis2[i]) {
if (subtree_size[i] > N / 2) {
works = false;
return dfs2(i);
}
}
}
if (works) {
// cout<<"yay "<<n<<endl;
return n;
}
return -1;
}
vi order;
bool vis3[100005];
void dfs3(int n) {
vis3[n] = true;
order.pb(n);
for (int i : adj[n]) {
if (!vis3[i]) {
dfs3(i);
}
}
}
int main() {
cin>>N;
for (int i = 0; i < N - 1; i++) {
int u, v;
cin>>u>>v;
u--; v--;
edges.pb({u, v});
adj[u].pb(v);
adj[v].pb(u);
}
dfs(0);
/*
cout<<"subtree size: ";
for (int i = 0; i < N; i++) {
cout<<subtree_size[i]<<" ";
}
cout<<endl;
*/
ll total = 0;
for (int i = 0; i < N - 1; i++) {
int u = edges[i].fi;
int v = edges[i].se;
if (subtree_size[u] < subtree_size[v]) // u is parent of v
swap(u, v);
total += min(subtree_size[v], N - subtree_size[v]);
}
total *= 2;
int centroid = dfs2(0); // find centroid
// cout<<"centroid: "<<centroid<<endl;
dfs3(centroid); // need order
/*
cout<<"order: ";
for (int i : order)
cout<<i<<" ";
cout<<endl;
*/
int ans[N];
if (N % 2 == 0) {
for (int i = 0; i < N / 2; i++) {
ans[order[i]] = order[i + N / 2];
ans[order[i + N / 2]] = order[i];
}
}
else {
ans[order[0]] = order[0];
for (int i = 0; i < N / 2; i++) {
ans[order[i + 1]] = order[i + N / 2 + 1];
ans[order[i + N / 2 + 1]] = order[i + 1];
}
swap(ans[order[0]], ans[order[1]]);
}
// cout<<"ANSWER: "<<endl;
if (N <= 10) {
bruteforce();
}
else {
minimumans.fi = 0;
minimumans.se = vi(N, 1);
}
cout<<minimumans.fi<<" "<<total<<endl;
for (int i = 0; i < N; i++) {
cout<<(minimumans.se[i] + 1)<<" ";
}
cout<<endl;
for (int i = 0; i < N; i++) {
cout<<(ans[i] + 1)<<" ";
}
cout<<endl;
}
// find centroid, do dfs order, then map i to i + N / 2
// only important is that start and end never belong to same tree
// n = 8: (1, 2, 3, 4) <=> (5, 6, 7, 8)
// n = 9: (2, 3, 4, 5) <=> (6, 7, 8, 9), then swap the "goto" for
// 1 and 2 (then 1 -> 1 and 2 -> 6 becomes 1 -> 6 and 2 -> 1)
