#include <bits/stdc++.h>
#include "icc.h"
#include <vector>
using namespace std;
#define pb push_back
const int MAXN=100+5;
int par[MAXN],sz[MAXN];
int find(int x){
return par[x]=(par[x]==x?x:find(par[x]));
}
void merge(int a,int b){
a=find(a);
b=find(b);
if(sz[a]>sz[b])swap(a,b);
par[a]=b;
sz[b]+=sz[a];
}
vector<int> vec[MAXN];
int Query(vector<int> a,vector<int> b,bool flag){
if(flag){
vector<int> c,d;
for(auto i:a){
for(auto j:vec[i])c.pb(j);
}
for(auto i:b){
for(auto j:vec[i])d.pb(j);
}
a=c; b=d;
}
int arr[a.size()],arrb[b.size()];
for(int i=0;i<a.size();i++)arr[i]=a[i];
for(int i=0;i<b.size();i++)arrb[i]=b[i];
return query(a.size(),b.size(),arr,arrb);
}
pair<int,int> start(vector<int> a,vector<int> b,bool flag){
if(a.size()==1 && b.size()==1)return {a[0],b[0]};
if(a.size()==1)swap(a,b);
vector<int> c;
for(int i=a.size()-1;i>=a.size()/2;i--)c.pb(a[i]);
if(!Query(c,b,flag)){
c.clear();
for(int i=0;i<a.size()/2;i++)c.pb(a[i]);
}
if(b.size()==1)return start(c,b,flag);
vector<int> d;
for(int i=b.size()-1;i>=b.size()/2;i--)d.pb(b[i]);
if(Query(c,d,flag))return start(c,d,flag);
d.clear();
for(int i=0;i<b.size()/2;i++)d.pb(b[i]);
return start(c,d,flag);
}
void run(int N) {
for(int i=1;i<=N;i++){
par[i]=i;
sz[i]=1;
}
std::random_device rd;
std::mt19937 g(rd());
for (int built = 0; built < N - 1; ++built) {
for(int i=1;i<=N;i++)vec[i].clear();
vector<int> all;
for(int i=1;i<=N;i++){
if(vec[find(i)].size()==0)all.pb(find(i));
vec[find(i)].pb(i);
}
vector<int> a,b;
while(1) {
std::shuffle(all.begin(), all.end(), g);
a.clear(); b.clear();
for(int i=0;i<all.size()/2;i++)a.pb(all[i]);
for(int i=all.size()/2;i<all.size();i++)b.pb(all[i]);
if(Query(a,b,1))break;
}
vector<int> c,d;
for(int i=0;i<a.size();i++){
for(auto j:vec[a[i]])c.pb(j);
}
for(int i=0;i<b.size();i++){
for(auto j:vec[b[i]])d.pb(j);
}
pair<int,int> ans=start(c,d,0);
merge(ans.first,ans.second);
setRoad(ans.first,ans.second);
}
}
