// Author: Teoman Ata Korkmaz
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
constexpr int N=2e5+5;
///////////////////////////////////////////////////////////
int n,centroid=-1,v_min[N],v_max[N],sz[N],depth[N],bl[N][19];
vector<int> adj[N];
inline void init_dfs(int node,int p){
// cerr<<"init_dfs: "<<node<<" "<<p<<endl;
static int d=0;d++;
depth[node]=d;
bl[node][0]=p;
sz[node]=1;
bool is_centroid=true;
for(int i:adj[node]){
if(i==p)continue;
init_dfs(i,node);
sz[node]+=sz[i];
is_centroid&=sz[i]<n/2;
}
is_centroid&=sz[node]>=n/2;
if(is_centroid)centroid=node;
d--;
}
inline void init_bl(){
for(int j=0;j<18;j++){
for(int i=0;i<n;i++){
bl[i][j+1]=bl[bl[i][j]][j];
}
}
}
inline int dfs_min(int node,int p){
// cerr<<"dfs_min: "<<node<<" "<<p<<endl;
int hold=-1;
for(auto i:adj[node]){
if(i==p)continue;
int in=dfs_min(i,node);
if(in!=-1){
if(hold==-1){
hold=in;
}
else{
v_min[in]=hold;
v_min[hold]=in;
}
}
}
if(hold==-1)return node;
else{
v_min[hold]=node;
v_min[node]=hold;
return -1;
}
}
inline void solve_min(){
int node=dfs_min(0,-1);
if(node!=-1){
assert(node==0);
int tactical=adj[0][0];
v_min[v_min[tactical]]=node;
v_min[node]=tactical;
}
}
inline void dfs_max(int node,int p,vector<int>& st){
// cerr<<"dfs_max: "<<node<<" "<<p<<endl;
st.push_back(node);
for(int i:adj[node]){
if(i==p)continue;
dfs_max(i,node,st);
}
}
inline void solve_max(){
// cerr<<"centroid: "<<centroid<<endl;
assert(centroid!=-1);
vector<int> bt{centroid};
for(int i:adj[centroid]){
dfs_max(i,centroid,bt);
}
assert(bt.size()==n);
for(int i=0;i<n;i++){
v_max[bt[i]]=bt[(i+(n+1)/2)%n];
}
}
inline int lca(int a,int b){
// cerr<<"lca: "<<a<<" "<<b<<endl;
if(depth[a]<depth[b])swap(a,b);
int diff=depth[a]-depth[b];
for(int i=0;i<19;i++){
if(diff&(1<<i))a=bl[a][i];
}
if(a==b)return a;
for(int i=19;i--;){
if(bl[a][i]!=bl[b][i]){
a=bl[a][i];
b=bl[b][i];
}
}
return bl[a][0];
}
inline int dist(int a,int b){
return depth[a]+depth[b]-2*depth[lca(a,b)];
}
signed main(void){
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
x--,y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
init_dfs(0,0);
init_bl();
solve_min();
solve_max();
int ans_min=0;
int ans_max=0;
for(int i=0;i<n;i++){
ans_min+=dist(i,v_min[i]);
ans_max+=dist(i,v_max[i]);
}
// cerr<<"depth: ";for(int i=0;i<n;i++)cerr<<depth[i]<<" ";cerr<<endl;
cout<<ans_min<<" "<<ans_max<<endl;
for(int i=0;i<n;i++)cout<<v_min[i]+1<<" ";cout<<endl;
for(int i=0;i<n;i++)cout<<v_max[i]+1<<" ";cout<<endl;
}
