#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;
vector <int> L[DIM];
int v[DIM],fth[DIM];
int n,i,x,y,sol_min;
void dfs (int nod, int tata){
fth[nod] = tata;
for (auto vecin : L[nod])
if (vecin != tata)
dfs (vecin,nod);
if (nod != 1 && v[nod] == nod){
sol_min += 2;
swap (v[nod],v[fth[nod]]);
}
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<n;i++){
cin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
for (i=1;i<=n;i++)
v[i] = i;
dfs (1,0);
for (i=1;i<=n;i++)
if (v[i] == i){
sol_min += 2;
if (i != 1)
swap (v[i],v[fth[i]]);
else swap (v[i],v[L[1][0]]);
}
cout<<sol_min<<" "<<0<<"\n";
for (i=1;i<=n;i++)
cout<<v[i]<<" ";
cout<<"\n";
for (i=1;i<=n;i++)
cout<<v[i]<<" ";
return 0;
}
