#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
vector<set<int>>childs;
dsu(int n){
root=vector<int>(n);
iota(root.begin(),root.end(),0);
siz=vector<int>(n,1);
childs=vector<set<int>>(n);
for(int i = 0;i<n;i++)
childs[i].insert(i);
}
bool unite(int x, int y){
x=findRoot(x);
y=findRoot(y);
if(x==y)
return 0;
if(siz[x]<siz[y]){
swap(x,y);
}
siz[x]+=siz[y];
root[y]=x;
for(int i : childs[y]){
childs[x].insert(i);
}
return 1;
}
int findRoot(int x){
if(x==root[x]){
return x;
}
return root[x]=findRoot(root[x]);
}
};
void run(int n){
dsu ds(n);
for(int i = 0;i<n-1;i++){
set<int>s;
for(int i = 0;i<n;i++){
s.insert(ds.findRoot(i));
}
vector<int>arr;
for(int i : s){
arr.push_back(i);
}
int x = arr.size();
vector<int>par1;
vector<int>par2;
int arr1[n];
int arr2[n];
int n1 = 0;
int n2 = 0;
while(1){
par1.clear();
par2.clear();
for(int i : arr){
par1.push_back(i);
}
for(int i = 0;i<x/2;i++){
int ind = rand()%par1.size();
swap(par1[ind],par1[par1.size()-1]);
par2.push_back(par1.back());
par1.pop_back();
}
n1 = 0;
n2 = 0;
for(int i = 0;i<par1.size();i++){
for(int v : ds.childs[par1[i]]){
arr1[n1++]=v+1;
}
}
for(int i = 0;i<par2.size();i++){
for(int v : ds.childs[par2[i]]){
arr2[n2++]=v+1;
}
}
if(query(n1,n2,arr1,arr2)){
break;
}
}
//now we bin search twice
//bin search on 1
int lo = 0;
int hi = n1;
while(lo<hi){
int mid = (lo+hi)/2;
int temparr[n];
for(int i = 0;i<=mid;i++){
temparr[i]=arr1[i];
}
if(query(mid,n2,temparr,arr2)){
hi=mid;
}
else{
lo=mid+1;
}
}
int a = arr1[lo];
lo=0;
hi=n2;
while(lo<hi){
int mid = (lo+hi)/2;
int temparr[n];
for(int i = 0;i<=mid;i++){
temparr[i]=arr2[i];
}
if(query(mid,n1,temparr,arr1)){
hi=mid;
}
else{
lo=mid+1;
}
}
int b = arr2[lo];
setRoad(a,b);
}
}
