#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(),v.end() #define pb push_back using i64 = long long; template<typename T> using vec = vector<T>; vec<vec<int>> adj; vec<int> mnvec,mxvec,siz,order; int mn,n; i64 mx; void mndfs(int node,int p){ for (auto x : adj[node]){ if (x == p) continue; mndfs(x,node); } if (n != 1 && mnvec[node] == node){ if (p != -1) swap(mnvec[node],mnvec[p]); else swap(mnvec[node],mnvec[adj[node][0]]); mn += 2; } } void mxdfs(int node,int p){ order.pb(node); for (auto x : adj[node]){ if (x == p) continue; mxdfs(x,node); siz[node] += siz[x]; mx += min(siz[x], n - siz[x]); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; adj.assign(n + 10,vec<int>()); siz.assign(n + 10,1); mnvec.assign(n + 10,0); mxvec.assign(n + 10,0); for (int i = 0; i < n-1; i++){ int u,v; cin >> u >> v; u--; v--; adj[u].pb(v); adj[v].pb(u); } iota(all(mnvec),0); mndfs(0,-1); mxdfs(0,-1); mx *= 2; for (int i = 0; i < n; i++){ mxvec[order[i]] = order[(i + n / 2) % n]; } cout << mn << " " << mx << endl; for (int i = 0; i < n; i++) cout << mnvec[i] + 1 << " "; cout << endl; for (int i = 0; i < n; i++) cout << mxvec[i] + 1 << " "; return 0; }