#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
int N, dp[100005][2], ans[100005], conn[100005], seen[100005]; // 0 = isolated, 1 = attached
vector<int> graph[100005], g2[100005];
vector<int> broken[100005], unbroken[100005];
vector<int> order;
void dfs(int x, int p) {
dp[x][1] = 0;
int mindiff = 2069696969;
for (int v : graph[x]) {
if (v != p) {
dfs(v, x);
int df = max(0, dp[v][0] + 1 - dp[v][1]);
if (mindiff > df) {
mindiff = df;
conn[x] = v;
}
if (dp[v][0] + 1 > dp[v][1]) {
broken[x].push_back(v);
dp[x][1] += dp[v][0] + 1;
} else {
unbroken[x].push_back(v);
dp[x][1] += dp[v][1];
}
}
}
dp[x][0] = dp[x][1] - mindiff;
//printf("dp[%d][0]: %d\ndp[%d][1]: %d\n", x, dp[x][0], x, dp[x][1]);
}
void dfs2(int x, int state) {
int keep = -1;
if (state == 0) {
keep = conn[x];
}
if (keep != -1) {
g2[x].push_back(keep);
g2[keep].push_back(x);
//printf("edge %d - %d added\n", x, keep);
dfs2(keep, 1);
}
for (int v : broken[x]) {
if (v != keep) {
dfs2(v, 0);
}
}
for (int v : unbroken[x]) {
if (v != keep) {
g2[x].push_back(v);
g2[v].push_back(x);
//printf("edge %d - %d added\n", x, v);
dfs2(v, 1);
}
}
}
void dfs3(int x, int p) {
seen[x] = 1;
order.push_back(x);
for (int v : g2[x]) if (v != p) dfs3(v, x);
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N-1; i++) {
int a, b;
scanf("%d %d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(1, 1);
dfs2(1, 0); // Create g2
for (int i = 1; i <= N; i++) {
if (!seen[i]) {
order.clear();
dfs3(i, i);
for (int j = 0; j < order.size(); j++) {
ans[order[j]] = order[(j+1)%order.size()];
}
}
}
printf("%d 69\n", 2 * (N-1-dp[1][0]));
for (int i = 1; i <= N; i++) {
if (i == 1) printf("%d", ans[i]);
else printf(" %d", ans[i]);
} printf("\n");
for (int i = 1; i <= N; i++) {
if (i == 1) printf("%d", ans[i]);
else printf(" %d", ans[i]);
} printf("\n");
}
