#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5;
int sizee[MAX_N + 1], depth[MAX_N + 1], pairMinn[MAX_N + 1], pairMaxx[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int n;
int c;
void findCentroid( int u, int p ) {
int maxSizee = 0;
sizee[u] = 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
findCentroid( v, u );
sizee[u] += sizee[v];
maxSizee = max( maxSizee, sizee[v] );
}
maxSizee = max( maxSizee, n - sizee[u] );
if ( maxSizee <= n / 2 )
c = u;
}
void calcSizes( int u, int p ) {
sizee[u] = 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
calcSizes( v, u );
sizee[u] += sizee[v];
}
}
long long maxSumDist;
vector<int> vert;
void calcDepths( int u, int p ) {
depth[u] = depth[p] + 1;
maxSumDist += 2 * depth[u];
for ( int v: adj[u] ) {
if ( v == p )
continue;
calcDepths( v, u );
}
vert.push_back( u );
}
void getMaxSumDist() {
depth[0] = -1;
calcDepths( c, 0 );
for ( int i = 0; i < n / 2; i++ ) {
pairMaxx[vert[i]] = vert[n / 2 + i];
pairMaxx[vert[n / 2 + i]] = vert[i];
}
if ( pairMaxx[c] == 0 ) {
int a = adj[c][0], b = pairMaxx[a];
pairMaxx[a] = b;
pairMaxx[b] = c;
pairMaxx[c] = a;
}
}
long long minSumDist;
void dfs( int u, int p ) {
vector<int> unpaired;
sizee[u] = 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfs( v, u );
sizee[u] += sizee[v];
if ( pairMinn[v] == 0 )
unpaired.push_back( v );
}
if ( unpaired.size() >= 1 ) {
unpaired.push_back( u );
for ( int i = 0; i < (int)unpaired.size(); i++ )
pairMinn[unpaired[i]] = unpaired[(i + 1) % unpaired.size()];
minSumDist += 2 * (unpaired.size() - 1);
}
}
void getMinSumDist() {
minSumDist = 0;
dfs( c, 0 );
if ( pairMinn[c] == 0 ) {
int a = adj[c][0];
for ( int v: adj[c] ) {
if ( sizee[v] % 2 == 1 )
a = v;
}
int b = pairMinn[a];
pairMinn[a] = b;
pairMinn[b] = c;
pairMinn[c] = a;
if ( sizee[a] % 2 == 0 )
minSumDist += 2;
}
}
int main() {
cin >> n;
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
}
findCentroid( 1, 0 );
getMinSumDist();
getMaxSumDist();
cout << minSumDist << " " << maxSumDist << "\n";
for ( int v = 1; v <= n; v++ )
cout << pairMinn[v] << " ";
cout << "\n";
for ( int v = 1; v <= n; v++ )
cout << pairMaxx[v] << " ";
cout << "\n";
return 0;
}
