#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <cassert>
#include <random>
#include <chrono>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using ull = unsigned long long;
using ll = long long;
//#define int __int128
#define int ll
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define fr first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define vt vector
#define FOR(a, b) for(int i = (a); i <= (b); i++)
#define FORr(a, b) for(int i = (a); i >= (b); i--)
#define sz(x) (int)(x).size()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rangerng(int l, int r){
return uniform_int_distribution<>(l, r)(rng);
}
////////////////////////////////////////////////////////////////////////////////////
const int NMAX = 1e5;
int n;
vt <int> adj[NMAX + 1];
int minAns = 0;
int min_pos[NMAX + 1];
void dfs1(int node, int par){
for(int vec : adj[node]){
if(vec != par){
dfs1(vec, node);
}
}
if(min_pos[node] == node && node != 1){
swap(min_pos[node], min_pos[par]);
minAns += 2;
}
}
int maxAns = 0;
int max_pos[NMAX + 1];
int big[NMAX + 1];
void dfs2(int node, int par){
big[node] = 1;
for(int vec : adj[node]){
if(vec != par){
dfs2(vec, node);
big[node] += big[vec];
}
}
maxAns += min(big[node], n - big[node]);
}
int get_centroid(int node, int par){
for(int vec : adj[node]){
if(vec != par && big[vec] > n / 2){
return get_centroid(vec, node);
}
}
return node;
}
vt <int> aux;
void dfs3(int node, int par){
for(int vec : adj[node]){
if(vec != par){
dfs3(vec, node);
}
}
aux.pb(node);
}
void solve(){
cin >> n;
for(int i = 1; i <= n - 1; i++){
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
for(int i = 1; i <= n; i++){
min_pos[i] = i;
}
dfs1(1, 0);
if(min_pos[1] == 1){
int x = adj[1][0];
swap(min_pos[x], min_pos[1]);
minAns += 2;
}
dfs2(1, 0);
int centroid = get_centroid(1, 0);
for(int i = 1; i <= n; i++){
max_pos[i] = i;
}
dfs3(centroid, 0);
for(int i = 0; i < n / 2; i++){
swap(max_pos[aux[i]], max_pos[aux[n / 2 + i]]);
}
if(max_pos[centroid] == centroid){
swap(max_pos[centroid], max_pos[adj[centroid][0]]);
}
cout << minAns << ' ' << 2 * maxAns << '\n';
for(int i = 1; i <= n; i++){
cout << min_pos[i] << ' ';
}
cout << '\n';
for(int i = 1; i <= n; i++){
cout << max_pos[i] << ' ';
}
cout << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
//cin >> T;
T = 1;
while(T--){
solve();
}
return 0;
}
/*
4
1 2
2 3
3 4
7
4 2
5 7
3 4
6 3
1 3
4 5
*/
