#include "icc.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1e2+10;
int n;
int par[MAXN], p[MAXN];
vector <int> v[MAXN];
int subs[2][MAXN], sub_ind[2];
int pref[MAXN], lev[16][MAXN], cnt_lev[16], maxl;
int qa[MAXN], qb[MAXN];
int index_v[MAXN];
bool used[MAXN];
int qabr, qbbr, br;
int root(int x) {
if (par[x]==x) return x;
return par[x]=root(par[x]);
}
void add(int ind, int i) {
for (auto j:v[index_v[i]]) {
subs[ind][sub_ind[ind]]=j;
sub_ind[ind]++;
}
}
/*
int find_middle(int ql, int qr) {
if (ql+1==qr) return ql;
int l, r, mid;
l=ql; r=qr;
while (l<r) {
mid=(l+r)/2;
if ((pref[mid]-pref[ql-1])*2<=pref[qr]-pref[ql-1]) l=mid+1;
else r=mid;
}
return l-1;
}*/
void build_levels(int level, int l, int r) {
lev[level][cnt_lev[level]]=r-l+1;
cnt_lev[level]++;
if (l>=r) return;
maxl=max(maxl,level);
int mid=(l+r)/2;
build_levels(level+1,l,mid);
build_levels(level+1,mid+1,r);
}
void find_subsets() {
int level=1, cur_ind;
for (int i=0;i<12;i++) cnt_lev[i]=0;
pref[0]=0;
for (int i=1;i<br;i++) pref[i]=pref[i-1]+v[index_v[i]].size();
maxl=0;
build_levels(0,1,br-1);
while (level<=maxl) {
cur_ind=1;
sub_ind[0]=sub_ind[1]=0;
for (int i=0;i<cnt_lev[level];i++) {
for (int j=0;j<lev[level][i];j++,cur_ind++) add(i%2,cur_ind);
}
if (query(sub_ind[0],sub_ind[1],subs[0],subs[1])) return;
level++;
}
sub_ind[0]=sub_ind[1]=0;
for (int i=1;i<br;i++) add(i%2,i);
}
int find_vertex(int i, int j) {
qbbr=sub_ind[j];
for (int k=0;k<sub_ind[j];k++) qb[k]=subs[j][k];
int l, r, mid;
l=0; r=sub_ind[i]-1;
while (l<r) {
qabr=0;
mid=(l+r)/2;
for (int k=l;k<=mid;k++) {
qa[qabr]=subs[i][k];
qabr++;
}
if (query(qabr,qbbr,qa,qb)) r=mid;
else l=mid+1;
}
return subs[i][l];
}
void run(int N) {
n=N;
for (int i=1;i<=n;i++) par[i]=i;
int cnt=0;
while (cnt<n-1) {
for (int i=1;i<=n;i++) {
if (!v[i].empty()) v[i].clear();
}
for (int i=1;i<=n;i++) {
p[i]=root(i);
v[p[i]].push_back(i);
}
br=1;
for (int i=1;i<=n;i++) {
if (v[i].empty()) continue;
index_v[br]=i;
br++;
}
random_shuffle(index_v+1,index_v+br);
find_subsets();
random_shuffle(subs[0],subs[0]+sub_ind[0]);
random_shuffle(subs[1],subs[1]+sub_ind[1]);
int ansa=find_vertex(0,1);
int ansb=find_vertex(1,0);
setRoad(ansa,ansb);
par[root(ansa)]=root(ansb);
cnt++;
}
}
