#include "icc.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int fix[N],X,idx,n;
vector<pair<int,int> > edges;
vector<int> x,y,V[N],comp[N];
int solve(vector<int> x, vector<int> y){
int l = 0, r = (int)x.size() - 1, u;
while(l<=r) {
int mid = (l+r)/2;
int x1[mid+1],y1[y.size()];
for(int i = 0; i<=mid; i++) {
x1[i] = x[i];
}
for(int i = 0; i<y.size(); i++) {
y1[i] = y[i];
}
int f = query(mid+1,y.size(),x1,y1);
if(f) {
r = mid - 1;
u = x[mid];
}
else {
l = mid + 1;
}
}
return u;
}
void dfs(int u,int cur) {
comp[cur].push_back(u);
fix[u] = 1;
for(int i=0;i<V[u].size();i++) {
if(!fix[V[u][i]]) dfs(V[u][i],cur);
}
}
void in(vector<int> &x,int cur){
for(int i = 0; i<comp[cur].size();i++){
x.push_back(comp[cur][i]);
}
}
void run(int m){
n = m;
int lft = n - 1;
X = -1;
while(lft-- ){
X++;
for(int i=1;i<=n;i++) fix[i] = 0;
int cur = 0;
idx = 0;
for(int i=1;i<=n;i++) {
if(!fix[i]) {
comp[cur] .clear();
dfs(i,cur++);
}
}
vector<int> x,y;
for(int i=0; i<=log2(cur-1);i++) {
x.clear(); y.clear();
for(int j=0;j<cur;j++) {
if(j & (1<<i)) {
in(x,j);
}
else in(y,j);
}
int x1[x.size()],y1[y.size()];
for(int i = 0; i<x.size(); i++) x1[i] = x[i];
for(int i = 0; i<y.size(); i++) y1[i] = y[i];
if(query(x.size(),y.size(),x1,y1)) break;
}
int u = solve(x,y);
int v = solve(y,x);
setRoad(u,v);
V[u].push_back(v);
V[v].push_back(u);
}
}
