#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100'000;
int n;
int resMin[N + 10], ansMin;
int resMax[N + 10], root, cnt, sz[N + 10];
vector<int> base[N + 10], vec[N + 10], res[N + 10];
vector<int> adj[N + 10];
ll ansMax;
void readInput() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void calcSz(int u = 1, int par = 0) {
sz[u] = 1;
for (auto v: adj[u])
if (v != par) {
calcSz(v, u);
sz[u] += sz[v];
}
ansMax += (ll) min(sz[u], n - sz[u]) * 2ll;
}
int getCentroid() {
int res = 1;
while (true) {
int ok = res;
for (auto v: adj[res])
if (sz[v] < sz[res] && sz[v] > n / 2)
ok = v;
if (ok == res)
return res;
res = ok;
}
}
void addBase(int u, int par) {
base[cnt].push_back(u);
for (auto v: adj[u])
if (v != par)
addBase(v, u);
}
void calcBase(int root) {
base[++cnt].push_back(root);
vec[cnt] = base[cnt];
for (auto u: adj[root]) {
cnt++;
addBase(u, root);
vec[cnt] = base[cnt];
}
}
void calcResVectors() {
set<pair<int, int>> st;
for (int i = 1; i <= cnt; i++)
st.insert({base[i].size(), i});
while (st.size() >= 2) {
int idx1 = st.rbegin() -> second;
st.erase(*st.rbegin());
int idx2 = st.rbegin() -> second;
st.erase(*st.rbegin());
int ver1 = vec[idx1].back(), ver2 = vec[idx2].back();
res[idx1].push_back(ver2);
res[idx2].push_back(ver1);
vec[idx1].pop_back();
vec[idx2].pop_back();
if (vec[idx1].size())
st.insert({vec[idx1].size(), idx1});
if (vec[idx2].size())
st.insert({vec[idx2].size(), idx2});
}
if (st.size()) {
res[1].push_back(base[1][0]);
swap(res[2].back(), res[1].back());
}
}
void calcResMax() {
for (int i = 1; i <= cnt; i++)
for (int j = 0; j < base[i].size(); j++)
resMax[base[i][j]] = res[i][j];
}
void solveMax() {
calcSz();
root = getCentroid();
calcBase(root);
calcResVectors();
calcResMax();
}
int dfs(int u = 1, int par = 0) {
vector<int> vec;
for (auto v: adj[u])
if (v != par) {
int x = dfs(v, u);
if (x)
vec.push_back(x);
}
while (vec.size() > 2) {
int ver1 = vec.back();
vec.pop_back();
int ver2 = vec.back();
vec.pop_back();
swap(resMin[ver1], resMin[ver2]);
ansMin += 4;
}
if (vec.size() == 1) {
swap(resMin[u], resMin[vec[0]]);
ansMin += 2;
return 0;
}
if (vec.size() == 0 && u != 1)
return u;
if (vec.size()) {
int b1 = vec[0], b2 = vec[1];
swap(resMin[u], resMin[b1]);
swap(resMin[u], resMin[b2]);
ansMin += 4;
}
else {
swap(resMin[1], resMin[adj[u][0]]);
ansMin += 2;
}
return 0;
}
void solveMin() {
for (int i = 1; i <= n; i++)
resMin[i] = i;
dfs();
}
void writeOutput() {
cout << ansMin << ' ' << ansMax << '\n';
for (int i = 1; i <= n; i++)
cout << resMin[i] << ' ';
cout << '\n';
for (int i = 1; i <= n; i++)
cout << resMax[i] << ' ';
cout.flush();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
if (n == 1) {
cout << 0 << ' ' << 0 << '\n';
cout << 1 << '\n' << 1;
cout.flush();
return 0;
}
solveMax();
solveMin();
writeOutput();
return 0;
}
