#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>adj[maxn];
int n,m,sz[maxn],linkmax[maxn];
vector<vector<int>>allk;
long long res=0;
void dfs(int u,int par=0)
{
sz[u]=1;
for(auto x:adj[u]){
if(x!=par){
dfs(x,u);
sz[u]+=sz[x];
}
}
}
int findcen(int u,int ted,int par=0){
//cout<<u<<" "<<ted<<" "<<par<<" "<<sz[u]<<endl;
for(auto x:adj[u]){
if(x!=par&&sz[x]*2>=ted){
return findcen(x,ted,u);
}
}
//cout<<u<<endl;
return u;
}
int finds(){
dfs(1);
//cout<<"salam"<<endl;
return findcen(1,sz[1]);
}
int solve(int u,int rishe,int par=0){
if(u!=rishe){
allk.back().push_back(u);
}
int ret=1;
for(auto x:adj[u]){
if(x!=par){
if(u==rishe){
allk.push_back({});
}
int z=solve(x,rishe,u);
res+=2*z;
ret+=z;
}
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int r=finds();
//cout<<"salam"<<endl;
solve(r,r);
cout<<0<<" "<<res<<"\n";
for(int i=0;i<n;i++){
cout<<1<<" ";
}
cout<<"\n";
set<pair<int,int>>st;
for(int i=0;i<(int)allk.size();i++){
st.insert(make_pair((int)allk[i].size(),i));
}
//cout<<"salam"<<endl;
while((int)st.size()>1){
auto x=*st.rbegin();
st.erase(x);
auto y=*st.rbegin();
st.erase(y);
linkmax[allk[y.second].back()]=allk[x.second].back();
linkmax[allk[x.second].back()]=allk[y.second].back();
allk[x.second].pop_back();
allk[y.second].pop_back();
x.first--;
y.first--;
if(x.first>0){
st.insert(x);
}
if(y.first>0){
st.insert(y);
}
}
if((int)st.size()>0){
auto x=*st.rbegin();
int z=allk[x.second].back();
linkmax[z]=r;
linkmax[r]=z;
}
else{
if(r!=1){
linkmax[r]=1;
linkmax[linkmax[1]]=r;
}
else{
linkmax[r]=2;
linkmax[linkmax[2]]=r;
}
}
for(int i=1;i<=n;i++){
cout<<linkmax[i]<<" ";
}
cout<<"\n";
}
