#include <bits/stdc++.h> using namespace std; #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; void mndfs(int node,int p){ mnvec[zaman] = node; order[node] = zaman++; for (auto x : adj[node]){ if (x == p) continue; mndfs(x,node); } if (mnvec[order[node]] == node){ if (p != -1) swap(mnvec[order[node]],mnvec[order[p]]); else swap(mnvec[order[node]],mnvec[order[adj[node][0]]]); mn += 2; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; 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); } 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; }