Village

input/code.cpp:60:13: error: size of array 'dist' is not an integral constant-expression
   60 | int dist[n][n];
      |             ^
input/code.cpp:60:10: error: size of array 'dist' is not an integral constant-expression
   60 | int dist[n][n];
      |          ^
input/code.cpp: In function 'void dfs3(int, int, int, int)':
input/code.cpp:62:6: error: invalid types 'int[int]' for array subscript
   62 |     d[s][u] = d;
      |      ^
input/code.cpp: In function 'void solve()':
input/code.cpp:118:37: error: no match for 'operator<' (operand types are 'std::basic_ostream<char>' and 'char')
  118 |         for (int i: ans1) cout << i < ' ';
      |                           ~~~~~~~~~ ^ ~~~
      |                                |      |
      |                                |      char
      |                                std::basic_ostream<char>
input/code.cpp:118:37: note: candidate: 'operator<(int, int)' (built-in)
  118 |         for (int i: ans1) cout << i < ' ';
      |...

#include <bits/stdc++.h>

#define debug(x) cout << #x << ": " << x << endl

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 100100;

vector<int> adj[N];
ll n, ans;
vector<int> centr;
bool isc[N];

int dfs(int u, int p) {
    ll sz = 1;
    bool good = 1;
    for (int v: adj[u]) if (v != p) {
        ll sbsz = dfs(v, u);
        if (sbsz > n/2) good = 0;
        sz += sbsz;
    }
    
    if (n-sz > n/2) good = 0;
    if (good) centr.push_back(u);
    isc[u] = good;
    
    ans += min(sz, n-sz);
    return sz;
}

vector<vector<int>> sets;

void dfs2(int u, int p, int idx) {
    if (idx == -1) {
        sets.resize(adj[u].size());
        
        for (int i = 0; i < (int)adj[u].size(); ++i) {
            dfs2(adj[u][i], u, i);
        }
        return;
    }
    
    sets[idx].push_back(u);
    for (int v: adj[u]) if (v != p) {
        dfs2(v, u, idx);
    }
}

bool cmp(vector<int> &a, vector<int> &b) {
    return a.size() < b.size();
}

int dist[n][n];
void dfs3(int u, int p, int d, int s) {
    d[s][u] = d;
    for (int v: adj[u]) if (v != p) {
        dfs3(v, u, d+1, s);
    }
}

void solve() {
    cin >> n;
    
    if (n == 2) {
        cout << "2 2\n";
        cout << "2 1\n";
        cout << "2 1\n";
        return;
    }
    
    if (n <= 10) {
        vector<int> pos(n);
        for (int i = 0; i < n; ++i) {
            pos[i] = i;
        }
        
        for (int i = 0; i < n; ++i) {
            dfs3(i, -1, 0, i);
        }
        
        int opt1 = 1e9, opt2 = 0;
        vector<int> ans1, ans2;
        
        do {
            bool bad = 0;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (pos[i] == i) {
                    bad = 1;
                    break;
                }
                
                cnt += dist[i][pos[i]];
            }
            
            if (bad) continue;
            
            if (cnt < opt1) {
                opt1 = cnt;
                ans1 = pos;
            }
            
            if (cnt < opt2) {
                opt2 = cnt;
                ans2 = pos;
            }
            
        } while (next_permutation(all(pos)));
        
        cout << opt1 << ' ' << opt2 << '\n';
        for (int i: ans1) cout << i < ' ';
        cout << '\n';
        for (int i: ans2) cout << i < ' ';
        cout << '\n';
        return;
    }
    
    for (int i = 0; i < n-1; ++i) {
        int u, v;
        cin >> u >> v;
        --u;--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    dfs(0, -1);
    ans *= 2;
    
    vector<int> pos(n);
    if (centr.size() == 1) {
        int c = centr[0];
        dfs2(c, -1, -1);
        sort(rall(sets), cmp);
        
        pii i = {0, 0}, j = {0, n/2};
        while (j.se >= (int)sets[j.fi].size()) {
            j.se -= sets[j.fi].size();
            ++j.fi;
            j.fi %= sets.size();
        }
        
        while (j != make_pair(0, 0)) {
            pos[sets[i.fi][i.se]] = sets[j.fi][j.se];
            pos[sets[j.fi][j.se]] = sets[i.fi][i.se];
            
            ++i.se;
            if (i.se == (int)sets[i.fi].size()) {
                i.se = 0;
                ++i.fi;
                i.fi %= sets.size();
            }
            
            ++j.se;
            if (j.se == (int)sets[j.fi].size()) {
                j.se = 0;
                ++j.fi;
                j.fi %= sets.size();
            }
        }
        
        if (n&1) {
            pos[c] = c;
            swap(pos[c], pos[adj[c][0]]);
        } else {
            pos[c] = sets[i.fi][i.se];
            pos[sets[i.fi][i.se]] = c;
        }
    } else {
        int c = centr[0];
        dfs2(c, -1, -1);
        sort(rall(sets), cmp);
        sets[1].push_back(c);
        for (int i = 2; i < (int)sets.size(); ++i) {
            for (int j: sets[i]) {
                sets[1].push_back(j);
            }
        }
        
        for (int i = 0; i < n/2; ++i) {
            pos[sets[0][i]] = sets[1][i];
            pos[sets[1][i]] = sets[0][i];            
        }
    }
    
    cout << "0 " << ans << '\n';
    for (int i = 0; i < n; ++i) {
        cout << i+1 << ' ';
    }
    cout << '\n';
    for (int i = 0; i < n; ++i) {
        cout << pos[i]+1 << ' ';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}