#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>ans;
vector<vector<int>>graph;
int respuesta=0;
void dfs(int nodo, int p){
for(int u:graph[nodo]){
if(u!=p){
dfs(u,nodo);
}
}
if(ans[nodo]==nodo){
respuesta+=2;
if(p){
swap(ans[nodo],ans[p]);
}
else{
swap(ans[nodo],ans[graph[nodo][0]]);
}
}
}
int main() {
ll n;
cin>>n;
graph.resize(n+1,vector<int>());
for(int i=0;i<n-1;i++){
int a, b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
ans.resize(n+1);
for(int i=1;i<=n;i++){
ans[i]=i;
}
dfs(1,0);
cout<<respuesta<<" "<<respuesta<<"\n";
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<"\n";
}
