#include <bits/stdc++.h>
#include "tree.h"

using namespace std;

void solver(int n, int A, int B) {
    int root = 0 % n + 1;

    vector<int> dep(n + 1);
    vector<vector<int>> level(n + 1);

    for (int i = 1; i <= n; ++i) {
        if (i != root) {
            dep[i] = ask(root, {i});
        }
        level[dep[i]].push_back(i);
    }

    vector<int> fa(n + 1);
    vector dist(n + 1, vector<int>(n + 1));

    auto query = [&](int x, vector<int> a) {
        int ans = 0;
        for (int to : a) {
            ans += dist[x][to];
        }
        return ans;
    };

    vector<vector<int>> adj(n + 1);
    vector<int> tin(n + 1);
    vector<bool> used(n + 1);
    int T = 0;

    auto dfs = [&](auto self, int v) -> void {
        tin[v] = T++;
        for (int to : adj[v]) {
            self(self, to);
        }
    };

    used[1] = 1;

    constexpr int inf = 1e9 + 7;

    for (int l = 1; l <= n; ++l) {
        for (int x : level[l]) {
            int lx = 0, rx = level[l - 1].size();

            while (rx - lx > 1) {
                int mid = lx + rx >> 1;
                vector<int> L(level[l - 1].begin() + lx, level[l - 1].begin() + mid);

                int d = ask(x, L);
                int mn = min(lx == 0 ? inf : query(level[l - 1][lx - 1], L),
                             mid == level[l - 1].size() ? inf : query(level[l - 1][mid], L));

                if (d < mn) {
                    rx = mid;
                } else {
                    lx = mid;
                }
            }

            fa[x] = level[l - 1][lx];
            adj[fa[x]].push_back(x);
            used[x] = true;

            for (int to = 1; to <= n; ++to) {
                if (used[to]) {
                    dist[to][x] = dist[x][to] = (x == to ? 0 : dist[fa[x]][to] + 1);
                }
            }
        }

        T = 0;
        dfs(dfs, 0);
        sort(level[l].begin(), level[l].end(), [&](int x, int y) {
            return tin[x] < tin[y];
        });
    }

    for (int i = 1; i <= n; ++i) {
        if (i != root) {
            answer(i, fa[i]);
        }
    }
}