我们要给 $a$ 排序，考虑如何比较两个数 $a_u,a_v$。考察这样的构造：定一个异于 $u,v$ 的根 $rt$，连 $(rt,u)$ 和 $(u,v)$，对于其他点 $i$ 连 $(rt,i)$。若返回的最大独立集不包含 $rt$，则容易比较 $a_u,a_v$ 的大小关系。否则考虑调整，选择一个异于 $rt,u,v$ 的点 $p$，交换 $rt$ 和 $p$，再做一次询问。如果此时 $p$ 依然在最大独立集中，则可以推出 $a_u\leq a_v$。这是因为 $a_p\leq a_{rt}$，如果 $a_u>a_v$，我们把 $p,v$ 从独立集中删去，再把 $rt,u$ 加入独立集显然可以得到更大的独立集。

发现这个其实可以推广，一次性查询若干个不交的对 $(u_1,v_1),\cdots,(u_k,v_k)$ 的大小关系。方法是类似的：定一个根 $rt_1$ 和一个占位点 $rt_2$（注意保证 $\bm{a_{rt_1}\leq a_{rt_2}}$），连 $(rt_1,rt_2)$，然后对于每个询问对连 $(rt_1,u_i)$ 和 $(u_i,v_i)$，对于其他点 $i$ 连 $(rt_1,i)$。$rt_1,rt_2$ 容易通过 $1$ 次询问得到。这样我们就用 $1$ 次询问查询若干个对的大小关系。

考虑给除了 $rt_1,rt_2$ 之外的点排序。为了充分利用查询多个对的大小关系这一操作，我们需要一些并行程度较高的排序方法。这里引入奇偶归并排序。

::::info[奇偶归并排序]{open}

奇偶归并排序的核心操作是合并两个长度为 $2^k$ 的有序序列 $A,B$。具体来说：

• 取 $A,B$ 中的偶数项元素递归合并，得到长度为 $2^k$ 的有序序列 $E$。
• 取 $A,B$ 中的奇数项元素递归合并，得到长度为 $2^k$ 的有序序列 $O$。
• 交错排列 $E,O$：$E_0,O_0,E_1,O_1\cdots$。
• 对于每个 $0\leq i<2^k-1$，若 $O_i>E_{i+1}$ 则交换位置。

我们来证明这样合并的正确性。

:::info[正确性证明]

使用 0-1 principle，我们只需证明这样合并可以正确合并所有有序 $0/1$ 序列 $A,B$。设 $A$ 中有 $a$ 个 $0$，$B$ 中有 $b$ 个 $0$。设 $E$ 中有 $x=\lceil a/2\rceil+\lceil b/2\rceil$ 个 $0$，$O$ 中有 $y=\lfloor a/2\rfloor+\lfloor b/2\rfloor$ 个 $0$。显然 $0\leq x-y\leq 2$，不妨分类讨论其取值：

• $x-y\leq 1$：交错序列已经是有序的了。
• $x-y=2$：交错序列中唯一的逆序对为 $O_y=1,E_{y+1}=0$，显然这个逆序对会被交换。

因此得证。$\Box$

:::

接下来我们分析一下操作次数。

设合并两个长度为 $2^{k-1}$ 的有序序列的操作次数为 $T_{merge}(k)$，显然有 $T_{merge}(k)=T_{merge}(k-1)+1$，边界为 $T_{merge}(1)=1$，因此 $T_{merge}(k)=k$。

设给长度为 $2^k$ 的序列排序的操作次数为 $T_{sort}(k)$。我们将左右两半的长度为 $2^{k-1}$ 的序列分别排序，再合并起来。我们发现两边的排序可以并行，因此有 $T_{sort}(k)=T_{sort}(k-1)+T_{merge}(k)$，边界为 $T_{sort}(0)=0$，于是 $T_{sort}(k)=\dfrac{k(k+1)}2$。

::::

回到本题来看，不妨把 $n-2$ 补成 $2$ 的整数次幂，则排序的操作次数为 $\dfrac{\lceil\log_2(n-2)\rceil(\lceil\log_2(n-2)\rceil+1)}2$，取 $n=10^3$ 时操作次数为 $55$ 次。加上最开始找出 $rt_1,rt_2$ 的 $1$ 次询问，我们已经使用了 $56$ 次询问，还剩下 $14$ 次询问。

现在我们还需要把 $rt_1,rt_2$ 插入到排序好的 $n-2$ 个点中。对于单个点 $u$ 的插入，显然可以直接二分 $mid$，选择异于 $rt_1,rt_2,mid$ 的两个新的根节点 $rt_1',rt_2'$，然后比较 $a_u,a_{mid}$。但是一次二分就需要 $10$ 次比较，显然无法承受两次二分。容易想到把两次二分并行，每轮进行两次比较，如果 $mid_u,mid_v$ 相同则做调整使得它们不同。需要特判 $n=5$ 的情况，暴力做即可。

:::info[一些细节]{open}

简单说说上文中提到的调整。为了防止二分死循环，我们实际上要把 $mid_u$ 或者 $mid_v$ 像没搜索过的位置调整。以我的代码为例，可以这样实现：

while (lu < ru || lv < rv) {
	int midu = lu + ru >> 1, midv = lv + rv >> 1;
	if (lu < ru && lv < rv && midu == midv) {
		if (midv + 1 < rv) ++midv;
		else if (midu - 1 >= lu) --midu;
	}
	// ...
	if (...) ru = midu;
	else lu = midu + 1;
	if (...) rv = midv;
	else lv = midv + 1;
}

但是其实这样调整也可能有问题。存在 $mid_v+1=r_v\land mid_u=l_u$ 的情况，但是此时必然有 $l_u+1=r_u\land l_v+1=r_v$，所以直接让这两次比较分开做就行了。这样至多会产生 $1$ 次额外的询问。

:::

这部分操作次数至多为 $10+1=11$ 次，可以承受。

这样我们就用最多 $67$ 次操作解决了本题。

:::success[主要代码]

vector<int> sorting(int N) {
	n = N, rtu = 0, rtv = 1;
	vector<array<int, 2>> T;
	T.push_back({rtu, rtv});
	T.push_back({rtu, 2}), T.push_back({2, 3});
	for (int i = 4; i < n; ++i) T.push_back({rtu, i});
	auto vis = ask_question(T);
	if (!vis[rtu]) {
		if (!vis[2]) rtu = 2, rtv = 3;
		else rtu = 3, rtv = 2;
	} else swap(rtu, rtv);
	vector<int> vec;
	for (int i = 0; i < n; ++i) if (i != rtu && i != rtv) vec.emplace_back(i);
	int sz = vec.size();
	for (int p = 1, t = 1; p < sz; p <<= 1, ++t)
		for (int q = p; q >= 1; q >>= 1) {
			int r = q < p ? q : 0;
			vector<array<int, 2>> E;
			vector<pii> pairs;
			for (int i = r; i + q < sz; i += q << 1)
				for (int j = 0; j < q && i + j + q < sz; ++j)
					if ((i + j >> t) == (i + j + q >> t)) {
						E.push_back({vec[i + j], vec[i + j + q]});
						pairs.emplace_back(i + j, i + j + q);
					}
			if (!E.empty()) {
				auto res = compare(E, rtu, rtv);
				for (int k = 0; k < res.size(); ++k)
					if (!res[k]) swap(vec[pairs[k].first], vec[pairs[k].second]);
			}
		}
	int lu = 0, ru = sz, lv = 0, rv = sz;
	if (n == 5) {
		auto get_pos = [&](int x) {
			int l = 0;
			while (l < sz) {
				int rt1 = 0;
				while (rt1 == l) ++rt1;
				int rt2 = rt1 + 1;
				while (rt2 == l) ++rt2;
				auto res = compare({{x, vec[l]}}, vec[rt1], vec[rt2]);
				if (res[0]) return l;
				++l;
			}
			return l;
		};
		lu = get_pos(rtu), lv = get_pos(rtv);
	} else {
		while (lu < ru || lv < rv) {
			int midu = lu + ru >> 1, midv = lv + rv >> 1;
			if (lu < ru && lv < rv && midu == midv) {
				if (midv + 1 < rv) ++midv;
				else if (midu - 1 >= lu) --midu;
			}
			int rt1 = 0;
			while (rt1 == midu || rt1 == midv) ++rt1;
			int rt2 = rt1 + 1;
			while (rt2 == midu || rt2 == midv) ++rt2;
			vector<array<int, 2>> E;
			int id1 = -1, id2 = -1;
			if (lu < ru) id1 = E.size(), E.push_back({rtu, vec[midu]});
			if (lv < rv && (!~id1 || midu != midv)) id2 = E.size(), E.push_back({rtv, vec[midv]});
			auto res = compare(E, vec[rt1], vec[rt2]);
			if (~id1) res[id1] ? ru = midu : lu = midu + 1;
			if (~id2) res[id2] ? rv = midv : lv = midv + 1;
		}
	}
	vector<int> res;
	for (int i = 0; i <= sz; ++i) {
		if (lu == i) res.emplace_back(rtu);
		if (lv == i) res.emplace_back(rtv);
		if (i < sz) res.emplace_back(vec[i]);
	}
	return res;
}

:::