#include "icc.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
bool Query(vector<int> _A, vector<int> _B){
int a = _A.size(), b = _B.size();
int A[a], B[b];
for(int i = 0; i < a; i++) A[i] = _A[i]+1;
for(int i = 0; i < b; i++) B[i] = _B[i]+1;
return query(a, b, A, B);
}
void SetRoad(int a, int b){
setRoad(a+1, b+1);
}
void run(int n){
vector<vector<int>> comps(n);
for(int i = 0; i < n; i++) comps[i].pb(i);
for(int I = 0; I < n-1; I++){
int c = comps.size();
int k = 1, xr = 0;
while(k <= c-1){
vector<int> s0, s1;
for(int i = 0; i < c; i++){
if(i&k) for(int x: comps[i]) s1.pb(x);
else for(int x: comps[i]) s0.pb(x);
}
if(Query(s0, s1)) xr+=k;
k*=2;
}
vector<int> s;
for(int i = 0; i < c; i++){
if((i^xr) < i || (i^xr) >= c) continue;
s.pb(i);
}
int a = 0, b = int(s.size())-1;
while(a < b){
int md = (a+b)/2;
vector<int> s1, s2;
for(int i = 0; i <= md; i++){
for(int x: comps[s[i]]) s1.pb(x);
for(int x: comps[s[i]^xr]) s2.pb(x);
}
if(Query(s1, s2)) b = md;
else a = md+1;
}
int A = s[a], B = s[a]^xr;
a = 0, b = int(comps[B].size())-1;
while(a < b){
int md = (a+b)/2;
vector<int> ss(comps[B].begin(), comps[B].begin()+md+1);
if(Query(comps[A], ss)) b = md;
else a = md+1;
}
int node_b = comps[B][a];
a = 0, b = int(comps[A].size())-1;
while(a < b){
int md = (a+b)/2;
vector<int> ss(comps[A].begin(), comps[A].begin()+md+1);
if(Query(ss, {node_b})) b = md;
else a = md+1;
}
int node_a = comps[A][a];
SetRoad(node_a, node_b);
if(comps[A].size() < comps[B].size()) swap(comps[A], comps[B]);
while(!comps[B].empty()){
comps[A].pb(comps[B].back());
comps[B].pop_back();
}
comps.erase(comps.begin()+B);
}
}
