#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef set<int> si;
typedef set<long long> sll;
const ll MOD = 998244353;
const ld EPS = 1e-12;
#define endl "\n"
#define sp <<" "<<
#define forn(i, n) for(ll i = 0; i < n; i++)
#define rforn(i, n) for(ll i = n; i >= 0; i--)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
int N, LOGN;
ll mn = 0, mx = 0, timer = 0;
vector<int> ansMin, ansMax, depth, par;
vector<vector<int>> up;
unordered_map<int, set<int>> subt;
// mem this
void binLift(vector<vector<int>> &adj) {
for (int i = 0; i < N; i++) {
up[i][0] = par[i];
}
for (int j = 1; j < LOGN; j++) {
for (int i = 0; i < N; i++) {
if (up[i][j - 1] == -1) continue;
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
}
// mem this
int findLCA(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int i = 0; i < LOGN; i++) {
if (diff & (1 << i)) {
u = up[u][i];
}
}
// one is the ancestor of the other
if (u == v) {
return u;
}
// find last non-common ancestor
for (int i = 0; i < LOGN; i++) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
// mem this
int treeCenter(vector<vector<int>> &adj) {
vector<int> deg(N, 0);
vector<int> leaves;
for (int i = 0; i < N; i++) {
deg[i] = adj[i].size();
if (deg[i] == 0 || deg[i] == 1) {
leaves.push_back(i);
deg[i] = 0;
}
}
int count = leaves.size();
while (count < N) {
vector<int> newLeaves;
for (auto node : leaves) {
for (auto neighbor : adj[node]) {
deg[neighbor]--;
if (deg[neighbor] == 1) {
newLeaves.push_back(neighbor);
}
}
deg[node] = 0;
}
count += newLeaves.size();
leaves = newLeaves;
}
return leaves[0];
}
void findDepth(int node, int parent, int sub, int dep, vector<vector<int>> &adj, vector<int> &depth) {
if (sub == -2) sub = -1;
else if (sub == -1) sub = node;
subt[sub].insert(node);
depth[node] = dep;
for (auto neighbor : adj[node]) {
if (neighbor == parent) continue;
findDepth(neighbor, node, sub, dep + 1, adj, depth);
}
}
void minCase(int node, vector<vector<int>> &adj, vector<bool> &vis) {
int parent = -1;
for (auto neighbor : adj[node]) {
if (depth[neighbor] < depth[node]) {
parent = neighbor;
break;
}
}
// we are at an isolated root
if (parent == -1) {
vis[node] = true;
mn += 2;
swap(ansMin[node], ansMin[adj[node][0]]);
}
else {
vis[parent] = true;
for (auto neighbor : adj[parent]) {
if (depth[neighbor] < depth[parent]) {
par[parent] = neighbor;
continue;
}
par[neighbor] = parent;
if (vis[neighbor]) continue;
vis[neighbor] = true;
mn += 2;
swap(ansMin[parent], ansMin[neighbor]);
}
}
return;
}
void solution() {
cin >> N; LOGN = ceil(log2(N));
ansMin.resize(N), ansMax.resize(N), depth.resize(N), par.resize(N);
up.assign(N, vector<int>(LOGN, -1));
for (int i = 0; i < N; i++) {
ansMin[i] = i;
ansMax[i] = i;
}
vector<vector<int>> adj(N);
for (int i = 0; i < N - 1; i++) {
int u, v; cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
int center = treeCenter(adj);
findDepth(center, -1, -2, 0, adj, depth);
// min case
vector<bool> vis(N, false);
vector<pair<int, int>> depthCopy(N);
for (int i = 0; i < N; i++) {
depthCopy[i] = {depth[i], i};
}
sort(rall(depthCopy));
for (int i = 0; i < N; i++) {
if (!vis[depthCopy[i].second]) {
minCase(depthCopy[i].second, adj, vis);
}
}
// max case
par[center] = -1;
binLift(adj);
vis.assign(N, false);
depthCopy.clear(), depthCopy.resize(N);
for (int i = 0; i < N; i++) {
depthCopy.push_back({depth[i], i});
}
sort(rall(depthCopy));
priority_queue<pair<int, int>> pq;
for (auto x : adj[center]) {
pq.push({subt[x].size(), x});
}
bool flag1 = false;
while (!pq.empty()) {
pair<int, int> fir = pq.top(); pq.pop();
if (pq.empty()) {flag1 = true; pq.push(fir); break;}
pair<int, int> sec = pq.top(); pq.pop();
auto ele1 = subt[fir.second].begin(), ele2 = subt[sec.second].begin();
swap(ansMax[*ele1], ansMax[*ele2]);
mx += depth[*ele1] + depth[*ele2];
subt[fir.second].erase(ele1);
subt[sec.second].erase(ele2);
fir.first--; sec.first--;
if (fir.first > 0) pq.push(fir);
if (sec.first > 0) pq.push(sec);
}
if (flag1) {
bool flag2 = false;
int sub = pq.top().second;
while (!subt[sub].empty()) {
auto p1 = subt[sub].begin(); int ele1 = *p1; subt[sub].erase(ele1);
if (subt[sub].empty()) {flag2 = true; subt[sub].insert(ele1); break;}
auto p2 = subt[sub].begin(); int ele2 = *p2; subt[sub].erase(ele2);
swap(ansMax[ele1], ansMax[ele2]);
mx += depth[ele1] + depth[ele2] - 2 * depth[findLCA(ele1, ele2)];
}
if (flag2) {
auto ele1 = subt[sub].begin(); int ele2 = center;
swap(ansMax[*ele1], ansMax[ele2]);
mx += depth[*ele1] + depth[ele2];
} else {
swap(ansMax[center], ansMax[adj[center][0]]);
}
} else {
swap(ansMax[center], ansMax[adj[center][0]]);
}
// print the answer
cout << mn sp mx * 2 << endl;
for (int x : ansMin) cout << x + 1 << " ";
cout << endl;
for (int x : ansMax) cout << x + 1 << " ";
cout << endl;
return;
}
signed main() {
fast_io();
solution();
// int tests; cin >> tests;
// while (tests--) {
// solution();
// }
return 0;
}
