/*input
7
4 2
5 7
3 4
6 3
1 3
4 5
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ld double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e16;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
return ((a%MOD)*(b%MOD))%MOD;
}
ll mypow(ll a,ll b){
if(b<=0) return 1;
ll res=1LL;
while(b){
if(b&1) res=mult(res,a);
a=mult(a,a);
b>>=1;
}
return res;
}
set<int> v[maxn];
vector<int> v2[maxn];
int ans[maxn];
int rev[maxn];
int mx[maxn];
vector<int> pre;
ll mxx=0;
int n;
int dfs(int u,int p){
pre.pb(u);
int s=1;
for(int x:v[u]){
if(x!=p){
int z=dfs(x,u);
mxx+=min(z,n-z);
s+=z;
}
}
return s;
}
int32_t main(){
ios::sync_with_stdio(false),cin.tie(0);
queue<int> q;
cin>>n;
REP(i,n-1){
int a,b;
cin>>a>>b;
v[a].insert(b);
v[b].insert(a);
v2[a].pb(b);
v2[b].pb(a);
}
REP1(i,n){
ans[i]=rev[i]=i;
if(sz(v[i])==1) q.push(i);
}
dfs(1,-1);
int cnt=0;
while(!q.empty()){
int z=q.front();
q.pop();
if(!sz(v[z]) and ans[z]==z){
//cout<<z<<'\n';
int x=v2[z][0];
int k=rev[x];
ans[k]=z;
ans[z]=x;
rev[x]=z;
rev[z]=k;
cnt+=2;
}
for(int x:v[z]){
if(ans[z]==z){
int k=rev[x];
ans[k]=z;
ans[z]=x;
rev[x]=z;
rev[z]=k;
cnt+=2;
}
if(v[x].find(z)!=v[x].end()) v[x].erase(z);
//if(v[z].find(x)!=v[z].end()) v[z].erase(x);
if(sz(v[x])==1){
q.push(x);
}
}
v[z].clear();
}
cout<<cnt<<' '<<2*mxx<<'\n';
REP1(i,n) cout<<ans[i]<<' ';
cout<<'\n';
REP(i,sz(pre)){
mx[pre[i]]=pre[(i+n/2)%n];
}
REP1(i,n) cout<<mx[i]<<' ';
}
