#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int S[200005], cnt = 1, E[200005], p[20][200005];
vector <int> adj[200005];
int n, dep[200005], sz[200005], sz2[200005];
int mp[200006];
void dfs(int x, int par, int d){
S[x] = cnt++;
p[0][x] = par;
dep[x] = d;
sz[x] = 1, sz2[x] = d;
for(auto i : adj[x]){
if(i == par)continue;
dfs(i, x, d + 1);
sz[x] += sz[i];
sz2[x] += sz2[i];
}
E[x] = cnt - 1;
}
int lca(int u, int v){
if(dep[u] > dep[v])swap(u, v);
int diff = dep[v] - dep[u];
for(int i=19;i>=0;i--)if(diff >> i & 1)v = p[i][v];
if(u == v)return u;
for(int i=19;i>=0;i--){
if(p[i][u] != p[i][v])u = p[i][u], v = p[i][v];
}
return p[0][u];
}
int hv[200005], ans, bru[200005], f = 0;
void grr(int x, int par){
vector <int> tmp;
for(auto i : adj[x]){
if(i == par)continue;
grr(i, x);
if(hv[i])tmp.push_back(i);
}
bool g = 1;
if((int)tmp.size() >= 2 && (int)tmp.size()%2 == 0){
int xx = tmp.back(); tmp.pop_back();
int y = tmp.back(); tmp.pop_back();
ans += 2;
bru[x] = xx;
bru[xx] = y;
bru[y] = x;
f = 1;
g = 0;
}
while((int)tmp.size() >= 2){
int xx = tmp.back(); tmp.pop_back();
int y = tmp.back(); tmp.pop_back();
ans += 2;
bru[xx] = y, bru[y] = xx;
}
if(tmp.empty())hv[x] = g;
else ans++, bru[x] = tmp[0], bru[tmp[0]] = x;
}
struct node{
int s, e, m, val, pos, val2;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1;
val = 0, pos = s;
val2 = e - s + 1;
if(s != e)l = new node(s, m), r = new node(m+1, e);
}
void upd(int p, int v){
if(s == e){
val = v;
if(v == -1)val2--;
}
else{
if(p <= m)l->upd(p, v);
else r->upd(p, v);
val = max(l->val, r->val);
if(l->val >= r->val)pos = l->pos;
else pos = r->pos;
val2 = l->val2 + r->val2;
}
}
pi qry(int a, int b){
if(s == a && e == b)return {val, pos};
else if(b <= m)return l->qry(a, b);
else if(a > m)return r->qry(a, b);
else return max(l->qry(a, m), r->qry(m+1, b));
}
int qr(int a, int b){
if(a == s && b == e)return val2;
else if(b <= m)return l->qr(a, b);
else if(a > m)return r->qr(a, b);
else return l->qr(a, m) + r->qr(m+1, b);
}
}*root;
int bru2[200005], ans2, ded[200005];
void grr2(int xx, int par){
priority_queue <pi> pq;
for(auto i : adj[xx]){
if(i == par)continue;
if(root->qry(S[i], E[i]).fi > -1)pq.push({root->qr(S[i], E[i]), i});
}
while((int)pq.size() > 1){
pi x = pq.top(); pq.pop();
pi y = pq.top(); pq.pop();
pi mx = root->qry(S[x.se], E[x.se]);
pi mx2 = root->qry(S[y.se], E[y.se]);
ans2 += mx.fi + mx2.fi - 2 * dep[xx];
root->upd(mx.se, -1);
root->upd(mx2.se, -1);
mx.se = mp[mx.se];
mx2.se = mp[mx2.se];
bru2[mx.se] = mx2.se;
bru2[mx2.se] = mx.se;
ded[mx.se] = ded[mx2.se] = 1;
sz[x.se]--;
sz[y.se]--;
x.fi--;
y.fi--;
if(x.fi)pq.push(x);
if(y.fi)pq.push(y);
}
if(!pq.empty() && !ded[xx]){
pi x = pq.top(); pq.pop();
pi mx = root->qry(S[x.se], E[x.se]);
ans2 += mx.fi - dep[xx];
root->upd(mx.se, -1);
mx.se = mp[mx.se];
sz[x.se]--;
bru2[xx] = mx.se;
bru2[mx.se] = xx;
ded[mx.se] = ded[xx] = 1;
}
for(auto i : adj[xx]){
if(i == par)continue;
grr2(i, xx);
}
}
int B[500005];
void solve(){
cin >> n;
for(int i=1;i<n;i++){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, -1, 1);
for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)p[i][j] = p[i-1][p[i-1][j]];
grr(1, -1);
root = new node(1, n);
for(int i=1;i<=n;i++)mp[S[i]] = i;
for(int i=1;i<=n;i++)root->upd(S[i], dep[i]);
if(hv[1]){
int x = adj[1][0];
int y = bru[x];
if(bru[y] == x){
ans++;
bru[1] = x, bru[x] = y, bru[y] = 1;
}
else{
int z = bru[y];
bru[z] = y;
bru[1] = x; bru[x] = 1;
ans++;
}
}
grr2(1, -1);
for(int i=1;i<=n;i++){
if(!bru2[i]){
int x = (i == n ? i - 1 : i + 1);
int y = bru2[x];
bru2[i] = x, bru2[x] = y, bru2[y] = i;
ans2 += (dep[x] + dep[i] - 2 * dep[lca(x, i)] + dep[i] + dep[y] - 2 * dep[lca(i, y)] - dep[x] - dep[y] + 2 * dep[lca(x, y)]) / 2;
}
}
cout << ans * 2 << ' ' << ans2 * 2 << '\n';
for(int i=1;i<=n;i++)cout << bru[i] << ' ';
cout << '\n';
for(int i=1;i<=n;i++)cout << bru2[i] << ' ';
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
