#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, i, j, k, a, b, ans[100010], A[100010], res, cent, sz[100010], dep[100010], in[100010], revin[100010], cnt, res2, ans2[100010], dist[11][11];
vector<int>adj[100010];
void dfs(int v, int par, int depth)
{
in[v]=++cnt;
dep[v]=depth;
sz[v]=1;
for(int i=0;i<adj[v].size();i++)
{
int p=adj[v][i];
if(p==par)continue;
dfs(p, v, depth+1);
sz[v]+=sz[p];
}
}
int centroid(int v, int par)
{
for(int i=0;i<adj[v].size();i++)
{
int p=adj[v][i];
if(p==par)continue;
if(sz[p]*2>n)
{
return centroid(p, v);
}
}
return v;
}
int f(int x)
{
return ((x+(n/2))%n==0?n:(x+(n/2))%n);
}
main()
{
for(scanf("%lld", &n);++i<n;)
{
scanf("%lld %lld", &a, &b);
adj[a].push_back(b);
adj[b].push_back(a);
if(n<=10)
{
dist[a][b]=dist[b][a]=1;
}
}
dfs(1, 0, 0);
cent=centroid(1, 0);
cnt=0;
dfs(cent, 0, 0);
for(i=0;i++<n;)res+=dep[i]*2;
for(i=0;i++<n;)
{
revin[in[i]]=i;
}
for(i=0;i++<n;)
{
ans[revin[i]]=revin[f(i)];
}
if(n<=10)
{
vector<int>v;
for(i=0;i++<n;)v.push_back(i);
for(i=0;i++<n;)
{
for(j=0;j++<n;)
{
if(dist[i][j]==0)dist[i][j]=1e9;
}
}
for(k=0;k++<n;)
{
for(i=0;i++<n;)
{
for(j=0;j++<n;)
{
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
}
}
}
res2=1e9;
do
{
int res3=0;
for(i=0;i++<n;)
{
if(v[i-1]==i)
{
goto next;
}
res3+=dist[i][v[i-1]];
}
if(res3<res2)
{
res2=res3;
for(i=0;i++<n;)ans2[i]=v[i-1];
}
next:;
}while(next_permutation(v.begin(), v.end()));
}
else
{
res2=1;
for(i=0;i++<n;)ans2[i]=1;
}
printf("%lld %lld\n", res2, res);
for(i=0;i++<n;)printf("%lld ", ans2[i]);
puts("");
for(i=0;i++<n;)
{
printf("%lld ", ans[i]);
}
}
