#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> #define int long long #define double long double #define pii pair<int, int> #define tiii tuple<int, int, int> #define tiiii tuple<int, int, int, int> #define emb emplace_back #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define iShowSpeed cin.tie(NULL)->sync_with_stdio(false) #define matrix vector<vector<int>> #define mat(n, m) vector<vector<int>>(n, vector<int>(m)); const int mod = 1e9+7; const int inf = 1e18; const matrix II = {{1, 0}, {0, 1}}; const int N = 2e5 + 5; int n, sum, sz[N], dis[N]; vector <int> order; vector <int> adj[N]; void dfssz(int u, int p){ // cout << u << " "; for (auto v : adj[u]) { if (v == p) continue; dfssz(v, u); sz[u] += sz[v]; } sz[u]++; } int centroid(int u, int p){ for (auto v : adj[u]) { if (v == p) continue; if (sz[v] >= n/2) return centroid(v, u); } return u; } void dfsdis(int u, int p){ order.emb(u); for (auto v : adj[u]) { if (v == p) continue; dis[v] = dis[u] + 1; dfsdis(v, u); } } void dfs(int u, int p){ int cnt = 0; for (auto v : adj[u]) { if (v == p) continue; if (sz[v] % 2) cnt++; dfs(v, u); } sum += 2 * (cnt/2); if (cnt % 2) sum++; } void solve() { n = 0, sum = 0; cin >> n; for (int i = 1; i <= n; i++) { sz[i] = 0; dis[i] = 0; adj[i].clear(); } for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].emb(v); adj[v].emb(u); } dfssz(1, 1); int c = centroid(1, 1); dfsdis(c, c); dfs(1, 1); vector <int> mxans(n + 1); if (n % 2) { mxans[order[0]] = order[1]; mxans[order[1]] = order[1 + n/2]; mxans[order[1 + n/2]] = order[0]; for (int i = 2; i < n - n/2; i++) { mxans[order[i]] = order[i + n/2]; mxans[order[i + n/2]] = order[i]; } } else { for (int i = 0; i < n - n/2; i++) { mxans[order[i]] = order[i + n/2]; mxans[order[i + n/2]] = order[i]; } } // cout << "MAX: " << accumulate(dis, dis + n + 1, 0ll) << "\n"; // cout << "MIN: " << sum << "\n"; cout << sum << " " << 2*accumulate(dis, dis + 1 + n, 0ll) << "\n"; for (int i = 1; i <= n; i++) cout << mxans[i] << " "; cout << "\n"; for (int i = 1; i <= n; i++) cout << mxans[i] << " "; } int32_t main() { iShowSpeed; solve(); }