#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
vector <int> gr[1001];
int Query(vector <int> a,vector<int> b){
const int sizA=a.size(),sizB=b.size();
int A[sizA], B[sizB];
for(int i=0;i<sizA;i++) A[i]=a[i];
for(int i=0;i<sizB;i++) B[i]=b[i];
int num=query(sizA,sizB,A,B);
return num;
}
int Query2(vector <int> A,vector<int> B){
vector <int> a,b;
for(int i:A){
for(int j:gr[i]) a.push_back(j);
}
for(int i:B){
for(int j:gr[i]) b.push_back(j);
}
return Query(a,b);
}
pair<vector <int>,vector <int>> Svec(vector <int> a){
vector <int> A1,A2;
for(int i=0;i<(int)a.size()/2;i++) A1.push_back(a[i]);
for(int i=(int)a.size()/2;i<a.size();i++) A2.push_back(a[i]);
return {A1,A2};
}
array<int,2> Solve_Case1_2(vector <vector<int>> grA,vector <vector<int>> grB);
array<int,2> Solve_Case2(vector <int> grA,vector <int> grB);
array<int,2> Solve_Case3(int A,int B);
array<int,2> Solve_Case1(vector <vector<int>> grA,vector <vector<int>> grB){
vector <int> allA,allB;
// cout<<"grA ";
for(vector <int> v:grA){
for(int i:v) {
allA.push_back(i);
// cout<<i<<" ";
}
}
// cout<<endl;
// cout<<"grB ";
for(vector <int> v:grB){
for(int i:v){
allB.push_back(i);
// cout<<i<<" ";
}
}
// cout<<endl;
if(Query2(allA,allB)==0){
vector <vector<int>> nwA,nwB;
for(vector <int> v:grA){
auto [cA,cB]=Svec(v);
nwA.push_back(cA);
nwB.push_back(cB);
}
for(vector <int> v:grB){
auto [cA,cB]=Svec(v);
nwA.push_back(cA);
nwB.push_back(cB);
}
return Solve_Case1(nwA,nwB);
}
else{
//cout<<"YES"<<endl;
return Solve_Case1_2(grA,grB);
}
}
array<int,2> Solve_Case1_2(vector <vector<int>> grA,vector <vector<int>> grB){
int l=0,r=grA.size()-1;
while(l<r){
int mid=(l+r)/2;
vector <int> allA,allB;
for(int j=l;j<=r;j++){
for(int i:grA[j]) allA.push_back(i);
}
for(int j=l;j<=r;j++){
for(int i:grB[j]) allB.push_back(i);
}
if(Query2(allA,allB)==1) r=mid;
else l=mid+1;
}
return Solve_Case2(grA[r],grB[r]);
}
array<int,2> Solve_Case2(vector <int> grA,vector <int> grB){
if(grA.size()==1&&grB.size()==1) return Solve_Case3(grA[0],grB[0]);
if(grA.size()==1) swap(grA,grB);
auto [grA1,grA2]=Svec(grA);
auto [grB1,grB2]=Svec(grB);
if(Query2(grA1,grB)==1){
if(grB.size()==1) return Solve_Case2(grA1,grB);
if(Query2(grA1,grB1)==1) return Solve_Case2(grA1,grB1);
else return Solve_Case2(grA1,grB2);
}
else{
if(grB.size()==1) return Solve_Case2(grA2,grB);
if(Query2(grA2,grB1)==1) return Solve_Case2(grA2,grB1);
else return Solve_Case2(grA2,grB2);
}
}
array<int,2> Solve_Case3(int A,int B){
//cout<<A<<" "<<B<<endl;
int l=0,r=gr[A].size()-1,posA=-1,posB=-1;
while(l<r){
int mid=(l+r)/2;
vector <int> qu;
for(int i=l;i<=mid;i++) qu.push_back(gr[A][i]);
if(Query(qu,gr[B])==1) r=mid;
else l=mid+1;
}
posA=gr[A][r];
l=0,r=gr[B].size()-1;
while(l<r){
int mid=(l+r)/2;
vector <int> qu;
for(int i=l;i<=mid;i++) qu.push_back(gr[B][i]);
if(Query(qu,gr[A])==1){
posB=mid;
r=mid;
}
else l=mid+1;
}
posB=gr[B][r];
return {posA,posB};
}
set <int> leaders;
int parent[1001];
int find(int i){
if(parent[i]==i) return i;
return parent[i]=find(parent[i]);
}
void merge(int a,int b){
a=find(a),b=find(b);
leaders.erase(b);
while(gr[b].size()!=0){
gr[a].push_back(gr[b].back());
gr[b].pop_back();
}
parent[b]=a;
return;
}
void run(int n){
//cout<<"YES"<<endl;
for(int i=1;i<=n;i++){
leaders.insert(i);
parent[i]=i;
gr[i].push_back(i);
}
int k=n-1;
while(k--){
vector <int> v;
for(int i:leaders) v.push_back(i);
vector <vector<int>> a,b;
a.push_back(Svec(v).first);
b.push_back(Svec(v).second);
auto [s,e]=Solve_Case1(a,b);
// cout<<s<<" "<<e<<endl;
merge(s,e);
setRoad(s,e);
}
//g++ -std=c++17 grader.cpp solve.cpp -o exe && ./exe
return;
}
