#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;
void dfs(int v, int p) { //return {v, odl}
vector<int> synowie;
for (int s : graf[v]) {
if (s != p) {
dfs(s, v);
if (!choice1[s]) synowie.push_back(s);
}
}
//cout << v << ' ' << synowie.size() << '\n';
if (synowie.size() == 0) return;
if (synowie.size() % 2 == 0) {
int v2 = synowie.back();
synowie.pop_back();
int v3 = synowie.back();
synowie.pop_back();
choice1[v] = v2;
choice1[v2] = v3;
choice1[v3] = v;
ans1 += 4;
}
else {
choice1[v] = synowie.back();
choice1[synowie.back()] = v;
synowie.pop_back();
ans1 += 2;
}
while (synowie.size()) {
int v2 = synowie.back();
synowie.pop_back();
int v3 = synowie.back();
synowie.pop_back();
choice1[v2] = v3;
choice1[v3] = v2;
ans1 += 4;
}
}
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 = i;
}
//cout << v << '\n';
dfs(v, v);
if (choice1[v] == 0) {
int kto = 1;
for (int v2 = 1; v2 <= n; v2++) {
if (choice1[v2] == graf[v][0]) kto = v2;
}
choice1[kto] = v;
choice1[v] = graf[v][0];
ans1 += 2;
}
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;
}
