#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll M = 307;
const ll LG = 31;
ll n, m, k;
vector<ll>g[N];
vector<ll>res_mn, res_mx;
ll ans_mn = 0, ans_mx = 0;
bool used[N];
ll sz[N];
stack<ll>st[N];
bool useds[N];
bool comp(ll x, ll y) {
return st[x].size() < st[y].size();
}
multiset<ll, decltype(&comp)> s(&comp);
void dfs(ll v, ll par = -1) {
for (ll to : g[v]) {
if (to != par) {
dfs(to, v);
}
}
vector<ll>leaves;
for (ll to : g[v]) {
if (to != par) {
if (!used[to]) {
leaves.push_back(to);
}
}
}
if (leaves.size() != 0) {
ans_mn += leaves.size() * 2;
res_mn[v] = leaves[0];
for (ll i = 0; i < leaves.size() - 1; i++) {
res_mn[leaves[i]] = leaves[i + 1];
}
res_mn[leaves[leaves.size() - 1]] = v;
for (ll to : leaves) {
used[to] = true;
}
used[v] = true;
}
}
void calc_sz(ll v, ll par = -1) {
sz[v] = 1;
for (ll to : g[v]) {
if (to != par) {
calc_sz(to, v);
sz[v] += sz[to];
}
}
if (par != -1) {
ans_mx += 2 * min(ll(sz[v]), n - sz[v]);
}
}
ll centroid(ll v, ll par = -1) {
for (ll to : g[v]) {
if (to != par) {
if (sz[to] > n / 2) {
return centroid(to, v);
}
}
}
return v;
}
void inch_tenum_es_qci_stacki_mej(ll v, ll par, ll cur) {
if (!useds[v])st[cur].push(v);
for (ll to : g[v]) {
if (to != par) {
inch_tenum_es_qci_stacki_mej(to, v, cur);
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
ll leaf = 0;
for (ll i = 0; i < n - 1; i++) {
ll x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (ll v = 1; v <= n; v++) {
if (g[v].size() == 1) {
leaf = v;
break;
}
}
ll root = g[leaf][0];
res_mn.resize(n + 1, 0);
res_mx.resize(n + 1, 0);
dfs(root);
calc_sz(1);
ll c = centroid(1);
if (n % 2 != 0) {
ll cur_stack = 0;
for (ll to : g[c]) {
inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
}
ll maxim = 0;
for (ll i = 0; i < cur_stack; i++) {
if (comp(maxim, i)) {
maxim = i;
}
//cout << i << ": " << st[i].size() << endl;
}
ll v1 = st[maxim].top();
st[maxim].pop();
ll smaxim = 0;
for (ll i = 0; i < cur_stack; i++) {
if (comp(smaxim, i) && i != maxim) {
smaxim = i;
}
//cout << i << ": " << st[i].size() << endl;
}
ll v2 = st[smaxim].top();
st[smaxim].pop();
res_mx[c] = v1;
res_mx[v1] = v2;
res_mx[v2] = c;
useds[c] = useds[v2] = useds[v1] = true;
for (ll i = 0; i < cur_stack; i++) {
while (!st[i].empty()) {
st[i].pop();
}
}
}
ll cur_stack = 0;
for (ll to : g[c]) {
inch_tenum_es_qci_stacki_mej(to, c, cur_stack++);
}
ll minim = cur_stack;
if (!useds[c]) {
st[minim].push(c);
cur_stack++;
}
for (ll i = 0; i < cur_stack; i++) {
if(st[i].size()!=0)s.insert(i);
}
while (!s.empty()) {
//cout << s.size() << endl;
ll bg = *s.rbegin();
s.erase(--s.end());
ll sbg = *s.rbegin();
s.erase(--s.end());
ll v1 = st[bg].top();
ll v2 = st[sbg].top();
res_mx[v1] = v2;
res_mx[v2] = v1;
st[bg].pop();
st[sbg].pop();
if (st[bg].size() != 0) {
s.insert(bg);
}
if (st[sbg].size() != 0) {
s.insert(sbg);
}
//cout << bg << " " << sbg << endl;
}
cout << ans_mn << " " << ans_mx << endl;
for (ll v = 1; v <= n; v++) {
cout << res_mn[v] << " ";
}
cout << endl;
for (ll v = 1; v <= n; v++) {
cout << res_mx[v] << " ";
}
cout << endl;
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
