#include <bits/stdc++.h>
#include "icc.h"
using namespace std;;
#define ll long long
#define ar array
#define ld double
// #define int long long
#define all(v) v.begin(), v.end()
// #pragma GCC optimize("O3,Ofast,unroll-loops ")
const int N = 3010;
const int M = 20;
const int LOG = 20;
const int INF = 1e17;
int MOD = 1e9 + 7;
const ld EPS = 1e-12;
template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};
struct DSU{
vector<int> p;
DSU(int n){
p.resize(n);
iota(all(p), 0);
}
int fnd(int x){
if(p[x] == x)return x;
return p[x] = fnd(p[x]);
}
bool upd(int a,int b){
a = fnd(a);
b = fnd(b);
if(a == b)return 0;
p[a] = b;
return 1;
}
};
bool ask(vector<int> A, vector<int> B){
int n = A.size(), m = B.size();
int a[n], b[m];
for(int i = 0;i < n;i++)a[i] = A[i] + 1;
for(int i = 0;i < m;i++)b[i] = B[i] + 1;
return query(n, m, a, b);
}
void run(int n){
DSU dsu(n);
for(int it = 0;it < n - 1;it++){
map<int, vector<int> > mp;
for(int i = 0;i < n;i++)mp[dsu.fnd(i)].push_back(i);
vector<vector<int> > C;
int ind[n];
// int T = 0;
for(auto [a, b]: mp){
for(auto u: b)ind[u] = C.size();
C.push_back(b);
}
for(int j = 1;j < C.size();j *= 2){
vector<int> v[2];
for(int i = 0;i < C.size();i++){
for(auto u: C[i]){
if(j & i)v[1].push_back(u);
else v[0].push_back(u);
}
}
if(ask(v[0], v[1])){
swap(v[0], v[1]);
int lo = -1, hi = v[0].size() - 1;
while(hi - lo > 1){
int mid = (lo + hi) / 2;
vector<int> q;
for(int i = 0;i <= mid;i++)q.push_back(v[0][i]);
if(ask(q, v[1]))hi = mid;
else lo = mid;
}
int x = v[0][hi];
v[0] = {x};
vector<int> nv;
for(auto u: v[1]){
bool yes = 1;
for(int k = 1;k < j;k *= 2){
bool b1 = ind[x] & k;
bool b2 = ind[u] & k;
if(b1 != b2)yes = 0;
}
if(yes)nv.push_back(u);
}
v[1] = nv;
lo = -1, hi = v[1].size() - 1;
while(hi - lo > 1){
int mid = (lo + hi) / 2;
vector<int> q;
for(int i = 0;i <= mid;i++)q.push_back(v[1][i]);
if(ask(q, v[0]))hi = mid;
else lo = mid;
}
int y = v[1][hi];
setRoad(x + 1, y + 1);
dsu.upd(x, y);
break;
}
}
}
}
// signed main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int t = 1;
// // cin>>t;
// while (t--)orz();
// }
