#include <bits/stdc++.h>
#include "icc.h"
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct DSU {
vi p;
vector<vi> c;
DSU(int n) : p(n), c(n) {
forn(i, n) p[i] = i, c[i] = vi{i};
}
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (sz(c[x]) > sz(c[y])) swap(x, y);
for (int u : c[y]) c[x].pb(u);
c[y].clear(), p[y] = x;
return true;
}
};
bool ask(vector<ii> a, vector<ii> b) {
int A[sz(a)], B[sz(b)];
forn(i, sz(a)) A[i] = a[i].fst + 1;
forn(i, sz(b)) B[i] = b[i].fst + 1;
return query(sz(a), sz(b), A, B);
}
ii solve(vector<ii> &a, vector<ii> &b, int k) {
int lo = 0, hi = sz(b);
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (ask(a, vector<ii>(begin(b), begin(b) + mid))) hi = mid;
else lo = mid;
}
b = {b[lo]};
vector<ii> new_a;
forn(i, sz(a)) {
int flag = true;
forn(bit, k) if ((b.back().snd >> bit & 1) !=
(a[i].snd >> bit & 1)) {
flag = false;
}
if (flag) new_a.pb(a[i]);
}
a = new_a;
lo = 0, hi = sz(a);
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (ask(vector<ii>(begin(a), begin(a) + mid), b)) hi = mid;
else lo = mid;
}
a = {a[lo]};
return ii{a.back().fst, b.back().fst};
}
void run(int N) {
DSU dsu(N);
forn(_, N - 1) {
vector<vi> components;
forn(u, N) if (dsu.p[u] == u) components.pb(dsu.c[u]);
int bit = 0;
while ((1 << bit) < sz(components)) {
vector<ii> v[2];
forn(i, sz(components)) {
for (int u : components[i]) v[i >> bit & 1].eb(u, i);
}
if (ask(v[0], v[1])) {
auto [a, b] = solve(v[0], v[1], bit);
setRoad(a + 1, b + 1);
dsu.unite(a, b);
break;
}
bit++;
}
}
}
