// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(i , l , r) for (int i=l; i<=r; i+=1)
#define arc(i , r , l) for (int i=r; i>=l; i-=1)
const int N = 1e5+7;
int n,mn=0,mx=0 , A[N],s[N];
vector<int> e[N];
int mn_processor (int v , int p)
{
int child = 0 , sz=-1 , u=0;
vector<int> q;
for (auto to : e[v])
{
if (to == p){ continue; }
u=to;
if (mn_processor(to,v))
{
child++;++sz; q.push_back(to);
}
}
for (int i=0; i<=sz-1; i+=2)
{
A[q[i]]=q[i+1];
A[q[i+1]]=q[i];
}
if (child%2)
{
A[q.back()]=v;
A[v]=q.back();
s[v]=q.back();
}
mn += child<<1;
if (v==1 and child%2==0)
{
A[u] = v;
A[v] = s[u];
mn += 2;
}
return (child%2==0);
}
pair<int,int> mx_processor (int v , int p)
{
int sz = 1 , k = 1;
for (auto to : e[v])
{
if (to == p){ continue; }
auto [a,b] = mx_processor(to,v);
sz += a; k += b;
}
k = min(k,n-sz);
if (v!=1){ mx += 2*k; }
return {sz,k};
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
loop(i,1,n-1)
{
int u,v; cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
mn_processor(1,1);
mx_processor(1,1);
cout << mn << " " << mx << '\n';
loop(i,1,n)
{
cout << (A[i]==0?1:A[i]) << " ";
}
cout << '\n';
loop(i,1,n){ cout << 1 << " "; }
cout << '\n';
}
