#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; vec<int> order; int zaman,mn,mx,n; 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; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; adj.assign(n + 10,vec<int>()); order.assign(n + 10,0); 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); cout << mn << " " << mx << endl; for (int i = 0; i < n; i++) cout << mnvec[i] + 1 << " "; cout << endl; for (int i = 1; i <= n; i++) cout << i << " "; return 0; }