#include <iostream>
#include <vector>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
#define ff first
#define ss second
const int MAXN = 1e5 + 7;
vi graf[MAXN];
int choice1[MAXN];
ll ans1 = 0;
int sajz[MAXN];
void dfs1(int v,int p) {
sajz[v] = 1;
for (int s : graf[v]) {
if (s != p) {dfs1(s,v); sajz[v] += sajz[s];}
}
}
pii dfs(int v, int p) { //return {v, odl}
pii popv = {0, 0};
for (int s : graf[v]) {
if (s != p) {
pii infos = dfs(s, v);
if (!choice1[v] && infos.first) {
choice1[v] = infos.first;
choice1[infos.first] = v;
ans1 += infos.second * 2;
}
else if (infos.first && popv.first) {
choice1[infos.ff] = popv.ff;
choice1[popv.ff] = infos.ff;
ans1 += (popv.ss + infos.ss) * 2;
popv = {0, 0};
}
else if (infos.ff) popv = infos;
}
}
if (!choice1[v]) popv = {v, 0};
return {popv.ff, popv.ss + 1};
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a, b;
for (int i = 0; i < n - 1; i++) {
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
int v = 1;
for (int i = 1; i <= n; i++) {
if (graf[i].size() == 1) v = 1;
}
dfs1(v, v);
if (n % 2 == 1) {
vector<int> trojka = {v, graf[v][0]};
for (int s : graf[graf[v][0]]) {
if (sajz[s] % 2 == 1) {
trojka.push_back(s);
break;
}
}
choice1[trojka[0]] = trojka[1];
choice1[trojka[1]] = trojka[2];
choice1[trojka[2]] = trojka[0];
ans1 += 4;
}
dfs(v, v);
cout << ans1 << ' ' << ans1 << '\n';
for (int i = 1; i <= n; i++) {
cout << choice1[i] << ' ';
}
cout << '\n';
for (int i = 1; i <= n; i++) {
cout << choice1[i] << ' ';
}
cout << '\n';
return 0;
}
