#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
struct DSU{
vector<int>e;
void init(int n){
e=vector<int>(n,-1);
}
int get(int x){
return e[x]<0?x:e[x]=get(e[x]);
}
bool unite(int x, int y){
x=get(x); y=get(y);
if(x==y) return 0;
if(e[x]>e[y]) swap(x,y);
e[x]+=e[y];
e[y]=x;
return 1;
}
};
void run(int n){
DSU dsu;
dsu.init(n+5);
vector<int>bit={2,4,8,16,32,64,128};
for(int x=0;x<n-1;x++){
int layer=0;
int a[105];
int b[105];
int ptr=0;
int ptr2=0;
vector<int>nodes;
for(int y=1;y<=n;y++){
if(dsu.get(y)==y) nodes.push_back(y-1);
}
int need=lower_bound(bit.begin(),bit.end(),nodes.size())-bit.begin();
for(int y=0;y<=need;y++){
a.clear();
b.clear();
for(auto it:nodes){
if(it&(1<<y)){
a[ptr++]=it+1;
}
else{
b[ptr2++]=it+1;
}
}
if(query(ptr,ptr2,a,b)){
break;
}
}
//decomp
while(a.size()>1||b.size()>1){
//2 queries
int a1[105];
int b1[105];
int a2[105];
int b2[105];
int a11=0;
int a22=0;
int b11=0;
int b22=0;
for(int y=0;y<ptr;y++){
if(y%2){
//a1.push_back(a[y]);
a1[a11++]=a[y];
}
else{
//a2.push_back(a[y]);
a2[a22++]=a[y];
}
}
for(int y=0;y<ptr2;y++){
if(y%2){
//b1.push_back(b[y]);
b1[b11++]=b[y];
}
else{
//b2.push_back(b[y]);
b2[b22++]=b[y];
}
}
bool hold=query(a11,ptr2,a,b);
if(hold){
hold=query(a11,b11,a1,b1);
a=a1;
if(hold){
b=b1;
}
else{
b=b2;
}
}
else{
a=a2;
hold=query(a22,b11,a2,b1);
if(hold){
b=b1;
}
else b=b2;
}
}
dsu.unite(a[0],b[0]);
setRoad(a[0],b[0]);
}
}
