#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=3e5+5;
int deg[N];
set<int>st[N];
int ans[N];
vector<int>v[N];
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
ans[i]=i;
}
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
st[a].insert(b);
v[a].pb(b);
v[b].pb(a);
st[b].insert(a);
deg[a]++;
deg[b]++;
}
set<int>lf;
for(int i=1;i<=n;i++){
if(deg[i]==1){
lf.insert(i);
}
}
int cnt=0;
int s=0;
while(cnt<n-1){
cnt+=lf.size();
vector<int>add;
for(auto a:lf){
int p= *st[a].begin();
if(ans[a]==a){
swap(ans[a],ans[p]);
s+=2;
}
deg[p]--;
deg[a]--;
if(deg[p]==1){
add.pb(p);
}
}
cnt+=lf.size();
lf.clear();
for(auto x:add){
lf.insert(x);
}
}
cout<<s<<" "<<s<<endl;
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
}
