#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
void run(int N){
vector<int> comp[N+1];
for(int i = 1; i <= N; i++)
comp[i].push_back(i);
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();
}
vec.swap(tmp);
}
int l = 0, r = lft.size()-1;
while(l < r){
int mid = (l+r)>>1;
sza = 0;
for(int i = l; i <= mid; i++)
for(auto x : comp[lft[i]])
A[sza++] = x;
int res = query(sza,szb,A,B);
if(res) r = mid;
else l = mid+1;
}
sza = 0;
for(auto x : comp[lft[l]])
A[sza++] = x;
int a = lft[l];
l = 0, r = rht.size()-1;
while(l < r){
int mid = (l+r)>>1;
szb = 0;
for(int i = l; i <= mid; i++)
for(auto x : comp[rht[i]])
B[szb++] = x;
int res = query(sza,szb,A,B);
if(res) r = mid;
else l = mid+1;
}
int b = rht[l]; szb = 0;
for(auto x : comp[rht[l]])
B[szb++] = x;
l = 0, r = comp[a].size()-1;
while(l < r){
int mid = (l+r)>>1;
sza = 0;
for(int i = l; i <= mid; i++)
A[sza++] = comp[a][i];
int res = query(sza,szb,A,B);
if(res) r = mid;
else l = mid+1;
}
sza = 1;
A[0] = comp[a][l];
l = 0, r = comp[b].size()-1;
while(l < r){
int mid = (l+r)>>1;
szb = 0;
for(int i = l; i <= mid; i++)
B[szb++] = comp[b][i];
int res = query(sza,szb,A,B);
if(res) r = mid;
else l = mid+1;
}
szb = 1;
B[0] = comp[b][l];
setRoad(A[0],B[0]);
for(auto x : comp[b])
comp[a].push_back(x);
comp[b].clear();
}
}
