#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define fastio cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define siz size()
#define endl '\n'
const ll inf = 1e18;
const ll maxn=1e5+5455;
ll cen,n,sub[maxn],p[maxn],a[maxn],ans,cnt;
vector<ll>g[maxn],vec;
queue<ll>q;
void dfsz(ll v,ll par) {
sub[v]=1;
for(auto u:g[v]){
if(u==par)continue;
dfsz(u,v);
sub[v]+=sub[u];
}
if(v!=1)ans+=min(sub[v],n-sub[v]);
}
ll cent(ll v,ll par){
for(auto u:g[v]){
if(sub[u]*2>n && u!=par)return cent(u,v);
}
return v;
}
void dfs(ll v,ll par,ll r){
p[v]=r;
for(auto u:g[v]){
if(u!=par){
dfs(u,v,r);
}
}
}
void fill(ll v,ll par) {
vec.pb(v);
for(auto u:g[v]){
if(u!=par){
fill(u,v);
}
}
}
void dfss(ll v,ll par){
for(auto u:g[v]) {
if(u==par)continue;
dfss(u,v);
if(a[u]==u){swap(a[v],a[u]);cnt+=2;}
}
}
int main() {
cin>>n;
for(int i=1;i<n;i++){
ll u,v;cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
q.push(i);
}
q.push(n);
dfsz(1,-1);
cen=cent(1,-1);
vector<pll>x;
ll pp=ans;
dfsz(cen,-1);ans=pp;
for(auto v:g[cen]){
dfs(v,cen,v);
x.pb({sub[v],v});
}
sort(all(x));
reverse(all(x));
for(auto [j,v]:x){
vec.clear();
fill(v,cen);
for(auto u:vec){
while(a[u]==0){
ll b=q.front();
q.pop();
if(p[b]!=p[u])a[u]=b;
else q.push(b);
}
}
}
a[cen]=q.front();
if(a[cen]==cen){
swap(a[cen],a[g[cen][0]]);
}
ll c[n+2];
c[0]=ans*2;
for(int i=1;i<=n;i++){c[i]=a[i];a[i]=i;}
ll d[n+2];
dfss(1,-1);
if(a[1]==1){
cnt+=2;
ll u=g[1][0];swap(a[1],a[u]);
}
cout<<cnt<<" "<<c[0]<<endl;
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++)cout<<c[i]<<" ";
}
