#include <stdio.h>
#include <stdlib.h>
#define N 100000
int *ej[N], eo[N], n;
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int jj[N], pp[N], dd[N], mn;
void match(int i) {
while (dd[i] == 1) {
int j = jj[i], tmp;
if (pp[i] == i || dd[j] == 1)
tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
else
mn -= 2;
jj[i] ^= j, dd[i] = 0, jj[j] ^= i, dd[j]--;
i = j;
}
}
int sz[N], c;
void dfs1(int p, int i) {
int o, centroid;
sz[i] = 1, centroid = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j);
if (sz[j] * 2 > n)
centroid = 0;
sz[i] += sz[j];
}
}
if ((n - sz[i]) * 2 > n)
centroid = 0;
if (centroid)
c = i;
}
int qu[N], cnt; long long mx;
void dfs2(int p, int i, int d) {
int o;
mx += d * 2;
qu[cnt++] = i;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs2(i, j, d + 1);
}
}
int main() {
static int qq[N];
int h, i, j;
scanf("%d", &n);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (h = 0; h < n - 1; h++) {
scanf("%d%d", &i, &j), i--, j--;
append(i, j), append(j, i);
jj[i] ^= j, dd[i]++, jj[j] ^= i, dd[j]++;
}
for (i = 0; i < n; i++)
pp[i] = i;
mn = (n - 1) * 2;
for (i = 0; i < n; i++)
match(i);
dfs1(-1, 0);
dfs2(-1, c, 0);
for (i = 0; i <= (n - 1) / 2; i++)
qq[qu[i]] = qu[n / 2 + i], qq[qu[n / 2 + i]] = qu[i];
if (n % 2 == 1)
qq[qu[n - 1]] = qu[0];
printf("%d %lld\n", mn, mx);
for (i = 0; i < n; i++)
printf("%d ", pp[i] + 1);
printf("\n");
for (i = 0; i < n; i++)
printf("%d ", qq[i] + 1);
printf("\n");
return 0;
}
