#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
using ll = long long;
const ll INF = 1000000;
ll permutation[11];
void nextpermu(ll n)
{
ll swapa = n-1;
while (permutation[swapa]>permutation[swapa+1])
{
swapa--;
}
ll swapb=swapa+1;
for (ll i=swapa+1; i<=n; i++)
{
if (permutation[i]>permutation[swapa])
{
swapb=i;
}
}
ll swapper = permutation[swapa];
permutation[swapa]=permutation[swapb];
permutation[swapb]=swapper;
sort(permutation+swapa+1, permutation+n+1);
}
ll distanc[11][11];
ll visited[100005];
ll visitlist[100005];
void bfs(ll root, vector< vector<ll> > edgelist)
{
ll currindex = 0;
ll totalvisited = 1;
for (ll i=0; i<=11; i++)
{
visited[i]=0;
visitlist[i]=0;
}
visited[root]=1;
visitlist[1]=root;
while (currindex<totalvisited)
{
currindex++;
ll currnode = visitlist[currindex];
for (ll neigh: edgelist[currnode])
{
if (visited[neigh]==0)
{
totalvisited++;
visitlist[totalvisited]=neigh;
visited[neigh]=visited[currnode]+1;
distanc[root][neigh]=visited[currnode];
}
}
}
}
ll hipermu[11];
ll lopermu[11];
void solvesubtask1(ll n, vector< vector<ll> > edgelist)
{
hipermu[0]=0;
lopermu[0]=INF;
for (ll i=1; i<=n; i++)
{
bfs(i, edgelist);
}
while (permutation[1]>=1)
{
bool derangement = 1;
for (ll i=1; i<=n; i++)
{
if (permutation[i]==i)
derangement = 0;
}
if (derangement)
{
ll score = 0;
for (ll i=1; i<=n; i++)
{
score = score + distanc[i][permutation[i]];
}
if (score<lopermu[0])
{
lopermu[0]=score;
for (ll i=1; i<=n; i++)
{
lopermu[i]=permutation[i];
}
}
if (score>hipermu[0])
{
hipermu[0]=score;
for (ll i=1; i<=n; i++)
{
hipermu[i]=permutation[i];
}
}
}
nextpermu(n);
}
}
ll parent[100005];
ll subtreesize[100005];
ll centroidfinder(ll n, ll root, vector< vector<ll> > edgelist)
{
//copy of bfs
ll currindex = 0;
ll totalvisited = 1;
visited[root]=1;
visitlist[1]=root;
parent[root]=0;
while (currindex<totalvisited)
{
currindex++;
ll currnode = visitlist[currindex];
for (ll neigh: edgelist[currnode])
{
if (visited[neigh]==0)
{
totalvisited++;
visitlist[totalvisited]=neigh;
visited[neigh]=visited[currnode]+1;
parent[neigh]=currnode;
}
}
}
for (ll i=n; i>=1; i--)
{
ll currnode = visitlist[i];
subtreesize[currnode]++;
if ((2*subtreesize[currnode])>=n)
return currnode;
ll myparent = parent[currnode];
subtreesize[myparent]+=subtreesize[currnode];
}
return -1;//should not happen
}
void centroidbfs(ll n, ll centroid, vector< vector<ll> > edgelist)
{
ll currindex = 0;
ll totalvisited = 0;
for (ll i=1; i<=n; i++)
{
visited[i]=0;
visitlist[i]=0;
parent[i]=0;
subtreesize[i]=0;
}
visited[centroid]=1;//we dont want it to go to centroid
parent[centroid]=0;
//dfs one level then bfs the rest
for (ll child: edgelist[centroid])
{
//each time the loop runs, it starts and ends with currindex = totalvisited
parent[child]=centroid;
totalvisited++;
visited[child]=1;
visitlist[totalvisited]=child;
while (currindex<totalvisited)
{
currindex++;
ll currnode = visitlist[currindex];
for (ll neigh: edgelist[currnode])
{
if (visited[neigh]==0)
{
totalvisited++;
visitlist[totalvisited]=neigh;
visited[neigh]=1;
parent[neigh]=currnode;
}
}
}
}
visitlist[0]=centroid;
for (ll i=n-1; i>=1; i--)
{
ll currnode = visitlist[i];
subtreesize[currnode]++;
ll myparent = parent[currnode];
subtreesize[myparent]+=subtreesize[currnode];
}
subtreesize[centroid]=0;//obviously not true but it allows us to skip the centroid later in the calculation
}
long long largest = 0;
ll finalanswer[100005];
void solvelargest(ll n, vector< vector<ll> > edgelist)
{
ll acentroid = centroidfinder(n, 1, edgelist);
centroidbfs(n, acentroid, edgelist);
for (ll i=1; i<=n; i++)
{
long long trsize = subtreesize[i];
largest += trsize;
}
largest = largest*2;
for (ll i=0; i<=n-1; i++)
{
ll start = visitlist[i];
ll endindex = (i+(n/2))%n;
ll end = visitlist[endindex];
finalanswer[start]=end;
}
}
ll dp[100005][2];
//dp[i][0] is the answer for itself
//dp[i][1] is the answer for its children combined
bool carefor[100005];
//INF has been defined as 1M
ll small[100005];
ll total;
void vertexcover(ll n, ll root, vector< vector<ll> > edgelist)
{
//copy of bfs
//cout << "VERTEX COVER STARTED\n";
for (ll i=1; i<=n; i++)
{
visited[i]=0;
visitlist[i]=0;
parent[i]=0;
}
ll currindex = 0;
ll totalvisited = 1;
visited[root]=1;
visitlist[1]=root;
parent[root]=0;
vector< vector<ll> > children;
children.resize(n+1);
while (currindex<totalvisited)
{
currindex++;
ll currnode = visitlist[currindex];
for (ll neigh: edgelist[currnode])
{
if (visited[neigh]==0)
{
totalvisited++;
visitlist[totalvisited]=neigh;
visited[neigh]=visited[currnode]+1;
parent[neigh]=currnode;
children[currnode].push_back(neigh);
}
}
}
//cout << "BFS DONE\n";
for (ll i=n; i>=1; i--)
{
ll currnode = visitlist[i];
ll ansa = 0;
ll ansb = 0;
ll childrentaken = 0;
for (ll child: children[currnode])
{
ansb+=dp[child][0];
if (dp[child][0] >= (dp[child][1]+1))
{
childrentaken++;
ansa += (dp[child][1]+1);
}
else
{
ansa += dp[child][0];
}
}
if (children[currnode].size()==0)
{
ansa = INF;
}
else if (childrentaken == 0)
{
ansa++;
}
dp[currnode][0] = ansa;
dp[currnode][1] = ansb;
//cout << i << ' ' << currnode << ' ' << ansa << ' ' << ansb << '\n';
}
//cout << "DP DONE\n";
vector< vector<ll> > newedgelist;
newedgelist.resize(n+3);
carefor[root]=1;
for (ll i=1; i<=n; i++)
{
carefor[i]=1;
}
for (ll i=1; i<=n; i++)
{
ll currnode = visitlist[i];
//cout << currnode << '\n';
if (carefor[currnode])
{
//cout << "I CARE FOR THIS\n";
ll edgestaken = 0;
for (ll child: children[currnode])
{
//cout << "I HAVE A CHILD, IT IS " << child << '\n';
if (dp[child][0] >= (dp[child][1]+1))
{
edgestaken++;
newedgelist[currnode].push_back(child);
newedgelist[child].push_back(currnode);
//cout << "EDGE BETWEEN " << currnode << " AND " << child << '\n';
carefor[child]=0;
}
}
//cout << "YES YES YES\n";
if (edgestaken==0 and children[currnode].size()>0)
{
ll child = children[currnode][0];
carefor[child]=0;
//MAYBE THIS IS THE ERROR
for (ll grandchild: children[child])
{
carefor[grandchild]=1;
}
newedgelist[currnode].push_back(child);
newedgelist[child].push_back(currnode);
//cout << "EDGE BETWEEN " << currnode << " AND " << child << '\n';
}
//cout << "THIS IS DONE\n";
}
if (children[currnode].size()==0 and newedgelist[currnode].size()==0)
{
ll myparent = parent[currnode];
newedgelist[currnode].push_back(myparent);
newedgelist[myparent].push_back(currnode);
}
}
//cout << "NEWEDGELIST COMPLETE\n";
for (ll i=1; i<=n; i++)
{
visited[i]=0;
visitlist[i]=0;
parent[i]=0;
}
//implement dfs
total = 2*n;
ll check = 1;
while (check<=n)
{
if (visited[check]==0)
{
total--;
total--;
stack< vector<ll> > tovisit;
ll prev = check;
ll childcount = newedgelist[check].size();
vector<ll> childs;
childs.push_back(childcount);
for (ll i=0; i<childcount; i++)
{
childs.push_back(newedgelist[check][i]);
}
visited[check]=1;
tovisit.push(childs);
while (not tovisit.empty())
{
ll topsize = tovisit.top()[0];
if (topsize==0)
{
tovisit.pop();
}
else
{
ll nextchild = tovisit.top()[topsize];
tovisit.top()[0]--;
if (visited[nextchild]==0)
{
visited[nextchild]=1;
small[prev]=nextchild;
prev=nextchild;
ll childcountt = newedgelist[nextchild].size();
vector<ll> childss;
childss.push_back(childcountt);
for (ll i=0; i<childcountt; i++)
{
childss.push_back(newedgelist[nextchild][i]);
}
tovisit.push(childss);
}
}
}
small[prev]=check;
}
check++;
}
//cout << "DFS DONE AND PROCESS DONE\n";
}
int main()
{
ll n;
cin >> n;
vector< vector<ll> > edgelist;
edgelist.resize(n+1);
for (ll edge=1; edge<=(n-1); edge++)
{
ll a, b;
cin >> a >> b;
edgelist[a].push_back(b);
edgelist[b].push_back(a);
}
if (n<=0)
{
for (ll i=0; i<=n; i++)
{
permutation[i]=i;
}
solvesubtask1(n, edgelist);
cout << lopermu[0] << ' ' << hipermu[0] << '\n';
for (ll i=1; i<=n; i++)
{
cout << lopermu[i];
if (i==n)
{
cout << '\n';
}
else
{
cout << ' ';
}
}
for (ll i=1; i<=n; i++)
{
cout << hipermu[i];
if (i==n)
{
cout << '\n';
}
else
{
cout << ' ';
}
}
}
else
{
solvelargest(n, edgelist);
vertexcover(n, 1, edgelist);
cout << total << ' ' << largest << '\n';
for (ll i=1; i<=n; i++)
{
cout << small[i];
if (i==n)
{
cout << '\n';
}
else
{
cout << ' ';
}
}
for (ll i=1; i<=n; i++)
{
cout << finalanswer[i];
if (i==n)
{
cout << '\n';
}
else
{
cout << ' ';
}
}
}
}
