#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int INF=1e18;
int n,mn=0,mx=0;
vector<int> adj[N],v(N),v1(N,1);
void dfs(int k,int pa){
for(int j:adj[k]){
if(j==pa)continue;
dfs(j,k);
if(v[j]==j){
swap(v[j],v[k]);
mn+=2;
}
}
}
int32_t main() {
LCBorz;
cin>>n;
for(int i=1;i<n;i++){
int a,b;cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
iota(all(v),0);
dfs(1,1);
if(v[1]==1){
swap(v[1],v[adj[1][0]]);
mn+=2;
}
cout<<mn<<' '<<mx<<endl;
for(int i=1;i<=n;i++){
cout<<v[i]<<' ';
}
cout<<endl;
for(int i=1;i<=n;i++){
cout<<v1[i]<<' ';
}
cout<<endl;
return 0;
}
