import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Village {
static int masa[] = new int[100000];
static int masb[] = new int[100000];
static int degree[] = new int[100001];
static long neighboursum[] = new long[100001];
static int rinda[] = new int[100000];
static int subtree[] = new int[100001];
static int place[] = new int[100001];
static int fatchild[] = new int[100001];
static int order[] = new int[100000];
static int place2[] = new int[100001];
static int group[] = new int[100002];
static int groupSize[] = new int[100002];
static int counters[] = new int[100002];
static int n;
static int min(int a, int b) {
if (a < b) {
return a;
} else {
return b;
}
}
static StreamTokenizer in;
static PrintWriter out;
static int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws IOException {
in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
out = new PrintWriter(System.out);
n = nextInt();
for (int i = 0; i < n - 1; i++) {
masa[i] = nextInt();
masb[i] = nextInt();
degree[masa[i]]++;
degree[masb[i]]++;
neighboursum[masa[i]] += masb[i];
neighboursum[masb[i]] += masa[i];
}
int prieksa = 0;
int aste = 0;
for (int i = 1; i <= n; i++) {
subtree[i] = 1;
place[i] = i;
if (degree[i] == 1) {
rinda[prieksa] = i;
prieksa++;
}
}
while (prieksa > aste) {
int x = rinda[aste];
aste++;
int y = (int) neighboursum[x];
if (y > 0) {
if (fatchild[y] == 0 || subtree[fatchild[y]] < subtree[x]) {
fatchild[y] = x;
}
subtree[y] += subtree[x];
degree[y]--;
neighboursum[y] -= x;
if (degree[y] == 1) {
rinda[prieksa] = y;
prieksa++;
}
}
}
long minDistance = 0;
long maxDistance = 0;
for (int i = 0; i < n; i++) {
int x = rinda[i];
if (place[x] == x) {
int y = (int) neighboursum[x];
if (y > 0) {
place[x] = place[y];
place[y] = x;
minDistance += 2;
} else {
int j = i;
int z;
do {
j--;
z = rinda[j];
} while (j >= 0 && neighboursum[z] != x);
place[x] = place[z];
place[z] = x;
minDistance += 2;
}
}
}
for (int i = 1; i <= n; i++) {
maxDistance += 2 * min(subtree[i], n - subtree[i]);
}
out.print(minDistance);
out.print(" ");
out.println(maxDistance);
for (int i = 1; i <= n; i++) {
out.print(place[i]);
if (i < n) {
out.print(" ");
} else {
out.println();
}
}
// find centroid
int c = 1;
int cc = 1;
do {
c = cc;
if (subtree[c] < n / 2 + n % 2) {
cc = (int) neighboursum[c];
} else if (subtree[c] > n / 2) {
if (fatchild[c] != 0 && subtree[fatchild[c]] > n / 2) {
cc = fatchild[c];
}
}
} while (cc != c);
int nextGroup = 2;
for (int i = n - 1; i >= 0; i--) {
int x = rinda[i];
if ((x == c) || (neighboursum[x] == c)) {
group[x] = nextGroup;
nextGroup++;
} else if (neighboursum[x] > 0) {
group[x] = group[(int) neighboursum[x]];
} else {
group[x] = 1;
}
groupSize[group[x]]++;
}
for (int i = 1; i < nextGroup; i++) {
groupSize[i] += groupSize[i - 1];
}
for (int i = 1; i <= n; i++) {
order[groupSize[group[i] - 1] + counters[group[i]]] = i;
counters[group[i]]++;
}
for (int i = 0; i < n; i++) {
place2[order[i]] = order[(i + n / 2) % n];
}
for (int i = 1; i <= n; i++) {
out.print(place2[i]);
if (i < n) {
out.print(" ");
} else {
out.println();
}
}
out.flush();
}
}
