#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "icc.h"
using namespace __gnu_pbds;
using namespace std;
#define sz(v) (int)v.size()
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int MAXN = 105;
int p[MAXN], s[MAXN], a[MAXN], b[MAXN];
ordered_set st;
int find(int x){
if(p[x] == x)return x;
return p[x] = find(p[x]);
}
void merge(int a, int b){
a = find(a), b = find(b);
if(s[a] < s[b])swap(a,b);
st.erase( b );
p[b] = a;
s[a] += s[b];
}
mt19937 mt(time(0));
void run(int n){
for(int i = 1; i <= n; i++){
p[i] = i; s[i] = 1;
st.insert(i);
}
for(int z = 1; z < n; z++){
int pta, ptb;
vector<int> bits;
for(int i = 6; i >= 0; i--)
if( (sz(st)-1) & (1<<i) ){
for(int j = i; j >= 0; j--)bits.push_back(j);
break;
}
shuffle(bits.begin(), bits.end(), mt);
for(int i = 0; i < sz(bits); i++){
pta = 0, ptb = 0;
for(int j = 1; j <= n; j++){
int x = st.order_of_key(find(j));
if(x & (1<<bits[i])){ a[pta] = j; pta++; }
else { b[ptb] = j; ptb++; }
}
if(pta > 0 && ptb > 0){
int x = query(pta, ptb, a, b);
if(x == 1)break;
}
}
int la = 1, ra = pta;
while(la != ra){
int mid = (la+ra)/2;
if( query(mid, ptb, a, b) == 1)ra = mid;
else la = mid+1;
}
int lb = 1, rb = ptb;
while(lb != rb){
int mid = (lb+rb)/2;
if( query(pta, mid, a, b) == 1)rb = mid;
else lb = mid+1;
}
setRoad(a[la-1],b[lb-1]);
merge(a[la-1], b[lb-1]);
}
}
