#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
const int maxn=1e5+10;
vector<vi> graph(maxn);
vi sze(maxn,1);
void dfs(int cur, int prev=-1) {
for (auto to:graph[cur]) {
if (to==prev) {
continue;
}
dfs(to,cur);
sze[cur]+=sze[to];
}
}
vector<vi> dp(maxn,vi(2,1e9));
vi to(maxn,-1);
void dfs2(int cur, int prev=-1) {
if (graph[cur].size()==1 && cur!=0) {
dp[cur][1]=0;
return;
}
int cnt=0;
int diff=1e9;
for (auto to:graph[cur]) {
if (to==prev) {
continue;
}
dfs2(to,cur);
cnt+=min(dp[to][0],dp[to][1]+2);
if (dp[to][1]+2<=dp[to][0]) {
diff=0;
}
else {
diff=min(diff,dp[to][1]+2-dp[to][0]);
}
}
dp[cur][1]=cnt;
dp[cur][0]=cnt+diff;
}
pi dfs3(int ii, int cur, int prev=-1) {
vector<pi> out={{cur,cur}};
int t=-1;
if (ii==0 && dp[cur][0]!=dp[cur][1]) {
for (auto to:graph[cur]) {
if (to==prev) {
continue;
}
if (dp[to][1]+2-dp[to][0]==dp[cur][0]-dp[cur][1]) {
t=to;
break;
}
}
}
for (auto to:graph[cur]) {
if (to==prev) {
continue;
}
if (to==t || dp[to][1]+2<=dp[to][0]) {
out.pb(dfs3(1,to,cur));
}
else {
dfs3(0,to,cur);
}
}
int prv=out.size()-1;
for (int i=0; i<out.size(); i++) {
to[out[i].fi]=out[prv].se;
prv=i;
}
return {out[0].fi,to[out[0].fi]};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a,b;
for (int i=0; i<n-1; i++) {
cin >> a >> b;
graph[--a].pb(--b);
graph[b].pb(a);
}
dfs(0);
dfs2(0);
dfs3(0,0);
ll ans2=0;
for (int i=1; i<n; i++) {
ans2+=2*min(sze[i],n-sze[i]);
}
cout << dp[0][0] << ' ' << ans2 << '\n';
for (int i=0; i<n; i++) {
cout << to[i]+1 << " \n"[i==n-1];
}
for (int i=0; i<n; i++) {
cout << (i+1)%n+1 << " \n"[i==n-1];
}
return 0;
}
