#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
graph g(100005);
int tin[100005],tout[100005];
int dub[100005],up[20][100005],siz[100005];
int VREME=0;
void dfs(int p, int q)
{
tin[p]=++VREME,dub[p]=dub[q]+1,up[0][p]=q,siz[p]=1;
for (auto it : g[p]) if (it!=q) dfs(it,p),siz[p]+=siz[it];
tout[p]=VREME;
}
void build(int n)
{
ff(k,1,20) fff(i,1,n) up[k][i]=up[k-1][up[k-1][i]];
}
bool anc(int a, int b)
{
if (a==0) return true; if (b==0) return false;
return tin[a]<=tin[b] && tout[a]>=tout[b];
}
int Lca(int a, int b)
{
bff(k,0,20) if (!anc(up[k][a],b)) a=up[k][a];
if (!anc(a,b)) a=up[0][a]; return a;
}
int dist(int a, int b)
{
return dub[a]+dub[b]-2*dub[Lca(a,b)];
}
int find_centroid(int p, int q, int n)
{
int c=p;
for (auto it : g[p]) if (it!=q)
{
int tc=find_centroid(it,p,n);
if (tc!=-1) return tc;
if (2*siz[it]>n) c=-1;
}
if (2*(n-siz[p])>n) c=-1;
return c;
}
void poseti(int p, int q, vector<int> &dodaj)
{
dodaj.pb(p);
for (auto it : g[p])
if (it!=q) poseti(it,p, dodaj);
}
///ans arrays
int vel[100005];
int mal[100005];
void mfs(int p, int q)
{
for (auto it : g[p]) if (it!=q) mfs(it,p);
vector<int> spajam;
for (auto it : g[p]) if (it!=q) if (siz[it]%2==1) spajam.pb(it);
if (siz[p]%2==0) spajam.pb(p);
for (int i=1;i<(int)spajam.size();i+=2)
mal[spajam[i]]=spajam[i-1],mal[spajam[i-1]]=spajam[i];
}
bool vis[100005];
int deg[100005];
int main()
{
FAST;
int n; cin>>n;
ff(i,1,n)
{
int u,v; cin>>u>>v;
g[u].pb(v),g[v].pb(u);
}
dfs(1,0),tout[1]=VREME,build(n);
int c=find_centroid(1,0,n);
///veliki
vector<int> cor,big;
for (auto it : g[c])
{
if (2*max(siz[it],n-siz[it])<n) poseti(it,c,cor);
else poseti(it,c,big);
}
vector<int> border;
border.pb(c);
for (auto it : cor) border.pb(it);
for (auto it : big) border.pb(it);
ff(i,0,n) vel[border[i]]=border[(i+n/2)%n];
///mali
fff(i,1,n) mal[i]=i;
queue<int> bfs;
fff(i,1,n) if ((int)g[i].size()==1) bfs.push(i);
fff(i,1,n) deg[i]=(int)g[i].size();
while (!bfs.empty())
{
int p=bfs.front(); bfs.pop();
if (vis[p]) continue; vis[p]=1;
for (auto it : g[p]) if (!vis[it])
{
if (mal[p]==p) swap(mal[p],mal[it]);
deg[it]--; if (deg[it]==1) bfs.push(it);
}
}
fff(i,1,n) if (mal[i]==i)
{
swap(mal[i],mal[g[i][0]]);
}
///answer
li malans=0,velans=0;
fff(i,1,n) malans+=dist(i,mal[i]);
fff(i,1,n) velans+=dist(i,vel[i]);
cout<<malans<<" "<<velans<<"\n";
fff(i,1,n) cout<<mal[i]<<" "; cout<<"\n";
fff(i,1,n) cout<<vel[i]<<" "; cout<<"\n";
}
//Note to self: Check for overflow
/*
9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
7
7 3
4 7
1 7
7 2
5 7
7 6
*/
