#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100006;
int n, maxDepth[MAX], depth[MAX], childs[MAX];
vector<int> adj[MAX], c[MAX];
int nextShort[MAX], e[MAX], resShort;
int nextLong[MAX], resLong;
bool visited[MAX];
void dfs(int x, int prev = -1) {
for (auto &i: adj[x]) if (i != prev) {
c[x].push_back(i);
dfs(i, x);
}
}
void dfsShort(int x) {
e[x] = x;
vector<int> zero;
for (auto &i: c[x]) {
if (!childs[i]) zero.push_back(i), e[x] = i;
else {
dfsShort(i);
if (childs[i]) childs[x]--;
else zero.push_back(i), e[x] = i;
}
}
if (!childs[x]) return;
if (zero.empty()) return;
nextShort[x] = zero[0];
for (int i = 0; i < (int)zero.size(); i++) {
if (i != (int)zero.size() - 1) nextShort[zero[i]] = zero[i + 1];
else nextShort[zero[i]] = x;
resShort += 2;
}
}
void depthFrom(int x, int prev = -1) {
maxDepth[x] = depth[x];
for (auto &i: adj[x]) if (i != prev && !visited[i]) {
depth[i] = depth[x] + 1;
depthFrom(i, x);
maxDepth[x] = max(maxDepth[x], maxDepth[i]);
}
}
pair<int, int> farthest(int x, int prev = -1) {
for (auto &i: adj[x]) if (i != prev && !visited[i]) {
if (maxDepth[i] == maxDepth[x]) {
pair<int, int> t = farthest(i, x);
return { t.first, t.second + 1 };
}
}
return { x, 0 };
}
int main() {
scanf("%d", &n);
fill(nextShort, nextShort + n, -1);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d%d", &u, &v);
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0);
for (int i = 0; i < n; i++) childs[i] = (int)c[i].size();
dfsShort(0);
if (nextShort[0] == -1) {
nextShort[0] = c[0][0];
nextShort[e[c[0][0]]] = 0;
resShort += 2;
}
if (n > 1000) {
printf("%d 0\n", resShort);
for (int i = 0; i < n; i++) printf("%d ", nextShort[i] + 1);
puts("");
for (int i = 0; i < n - 1; i++) printf("%d ", i + 2);
printf("1");
return 0;
}
visited[0] = true;
int k = 0;
for (int i = 0; i < n - 1; i++) {
depth[k] = 0;
depthFrom(k);
pair<int, int> t = farthest(k);
nextLong[k] = t.first;
resLong += t.second;
k = t.first;
visited[k] = true;
}
for (int i = 0; i < n; i++) visited[i] = false;
depth[k] = 0;
depthFrom(k);
nextLong[k] = 0;
resLong += depth[0];
printf("%d %d\n", resShort, resLong);
for (int i = 0; i < n; i++) printf("%d ", nextShort[i] + 1);
puts("");
for (int i = 0; i < n; i++) printf("%d ", nextLong[i] + 1);
}
