#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int par[101];
int get(int u){
if(par[u]<0) return u;
return par[u]=get(par[u]);
}
void run(int N){
vector<int> comp[N+1];
for(int i = 1; i <= N; i++)
comp[i].push_back(i), par[i] = -1;
int A[N], B[N], sza, szb;
for(int _ = 1; _ < N; _++){
vector<vector<int>> vec(1);
for(int i = 1; i <= N; i++) if(!comp[i].empty())
vec[0].push_back(i);
vector<int> lft,rht;
for(; ;){
lft.clear(), rht.clear();
int cnt = 0;
for(auto x : vec){
for(int i = 0; i < (x.size()+cnt)/2; i++)
lft.push_back(x[i]);
for(int i = (x.size()+cnt)/2; i < x.size(); i++)
rht.push_back(x[i]);
cnt ^= 1;
}
sza = 0, szb = 0;
for(auto x : lft)
for(auto u : comp[x])
A[sza++] = u;
for(auto x : rht)
for(auto u : comp[x])
B[szb++] = u;
int res = query(sza,szb,A,B);
if(res) break;
vector<vector<int>> tmp;
cnt = 0;
for(auto x : vec){
tmp.push_back({});
for(int i = 0; i < (x.size()+cnt)/2; i++)
tmp.back().push_back(x[i]);
if(tmp.back().size()==1) tmp.pop_back();
tmp.push_back({});
for(int i = (x.size()+cnt)/2; i < x.size(); i++)
tmp.back().push_back(x[i]);
if(tmp.back().size()==1) tmp.pop_back();
cnt^=1;
}
vec.swap(tmp);
}
vector<int> tmp;
for(auto x : lft)
for(auto u : comp[x])
tmp.push_back(u);
swap(lft,tmp);
tmp.clear();
for(auto x : rht)
for(auto u : comp[x])
tmp.push_back(u);
swap(rht,tmp);
int szb = 0;
for(auto x : rht)
B[szb++] = x;
int l = 0, r = lft.size()-1;
while(l < r){
int mid = (l+r)>>1;
sza = 0;
for(int i = l; i <= mid; i++)
A[sza++] = lft[i];
if(query(sza,szb,A,B)) r = mid;
else l = mid+1;
}
int u = lft[l];
sza = 1, A[0] = u;
l = 0, r = rht.size()-1;
while(l < r){
int mid = (l+r)>>1;
szb = 0;
for(int i = l; i <= mid; i++)
B[szb++] = rht[i];
if(query(sza,szb,A,B)) r = mid;
else l = mid+1;
}
int v = rht[l];
setRoad(u,v);
u = get(u), v = get(v);
if(par[u]>par[v]) swap(u,v);
par[u] += par[v]; par[v] = u;
for(auto x : comp[v]) comp[u].push_back(x);
comp[v].clear();
}
}
