#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> > graph;
vector<int> match,prem;
vector<vector<int> > dp;
void dfs_min(int node,int parent){
for(auto x:graph[node]){
if(x==parent) continue;
dfs_min(x,node);
dp[node][0]+=max(dp[x][0],dp[x][1]);
}
for(auto x:graph[node]){
if(x==parent) continue;
if(dp[node][1]<dp[node][0]-max(dp[x][0],dp[x][1])+dp[x][0]+1){
dp[node][1]=dp[node][0]-max(dp[x][0],dp[x][1])+dp[x][0]+1;
prem[node]=x;
}
}
}
void dfs_match(int node,int parent,bool flag){
if(flag||dp[node][0]>=dp[node][1]){
for(auto x:graph[node]){
if(x==parent) continue;
dfs_match(x,node,0);
}
}
else{
match[node]=prem[node];
match[prem[node]]=node;
for(auto x:graph[node]){
if(x==parent) continue;
if(x==prem[node]) dfs_match(x,node,1);
else dfs_match(x,node,0);
}
}
}
int main(){
int n;
cin>>n;
graph.resize(n+1);
prem.resize(n+1);
int a,b;
for(int i=1;i<n;i++){
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dp.resize(n+1,vector<int>(2));
match.resize(n+1,-1);
dfs_min(1,0);
dfs_match(1,0,0);
vector<int> ans_min(n+1);
for(int i=1;i<=n;i++){
if(match[i]!=-1){
ans_min[i]=match[i];
}
else ans_min[i]=i;
}
int min_cnt=max(dp[1][1],dp[1][0])*2;
for(int i=1;i<=n;i++){
if(match[i]==-1){
swap(ans_min[i],ans_min[graph[i][0]]),min_cnt+=2;
}
}
cout<<min_cnt<<" 1\n";
for(int i=1;i<=n;i++) cout<<ans_min[i]<<" \n"[i==n];
for(int i=1;i<=n;i++) cout<<ans_min[i]<<" \n"[i==n];
}
