#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;

mt19937 rnd(chrono :: steady_clock :: now().time_since_epoch().count());
int depth[N], fa[N], dis[N][N];
vector<int> dep_vec[N];

void work(vector<int> up, vector<int> dn) {
	if (up.size() == 1) {
		for (auto x : dn) fa[x] = up[0];
		return;
	}
	if (dn.empty()) return;
	shuffle(up.begin(), up.end(), rnd);
	int mid = (up.size() >> 1);
	vector< pair<int, int> > nf, ns;
	nf.resize(up.size()); ns.resize(dn.size());
	vector<int> vec; vec.clear();
	for (int i = 0; i < mid; ++i) vec.push_back(up[i]);
	for (int i = 0; i < up.size(); ++i) {
		int o = 0;
		for (int j = 0; j < mid; ++j) o += dis[up[i]][up[j]] + 1;
		nf.push_back(make_pair(o, up[i]));
	}
	for (int i = 0; i < dn.size(); ++i) {
		int o = ask(dn[i], vec);
		ns.push_back(make_pair(o, dn[i]));
	}
	sort(nf.begin(), nf.end()); sort(ns.begin(), ns.end());
	vector<int> Fa, Sn;
	for (int i = 0, j = 0; i < nf.size();) {
		int k = i; Fa.clear(); Sn.clear();
		while (k < nf.size() && nf[k].first == nf[i].first) {
			Fa.push_back(nf[k].second);
			k++;
		}
		while (j < ns.size() && ns[j].first == nf[i].first) {
			Sn.push_back(ns[j].second);
			j++;
		}
		i = k;
		work(Fa, Sn);
	}
}

void solver(int n, int A, int B) {
	int rt = rnd() % n + 1;
	depth[rt] = 0;
	vector<int> vec;
	for (int i = 1; i <= n; ++i) {
		if (i == rt) continue;
		vec.clear(); vec.push_back(i);
		depth[i] = ask(rt, vec);
	}
	for (int i = 1; i <= n; ++i) dep_vec[depth[i]].push_back(i);
	for (int i = 1; i <= n; ++i) {
		work(dep_vec[i - 1], dep_vec[i]);
		for (auto x : dep_vec[i]) {
			dis[x][x] = 0;
			for (int j = 0; j < i; ++j)
				for (auto y : dep_vec[j])
					dis[x][y] = dis[y][x] = dis[fa[x]][y] + 1;
			for (auto y : dep_vec[i])
				if (x != y) dis[x][y] = dis[y][x] = dis[fa[x]][fa[y]] + 2;
		}
	}
	for (int i = 1; i <= n; ++i)
		if (i != rt) answer(fa[i], i);
}