#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[105];
void run(int n)
{
for (int i=1; i<n; i++)
{
vector<vector<int> > components;
queue<int> q;
int visited[n+5]={};
for (int j=1; j<=n; j++)
{
if (visited[j])
continue;
vector<int> tmp;
visited[j]=1;
q.push(j);
tmp.push_back(j);
while (!q.empty())
{
int u=q.front();
q.pop();
for (int v:adj[u])
{
if (!visited[v])
{
visited[v]=1;
q.push(v);
tmp.push_back(v);
}
}
}
components.push_back(tmp);
/*cout << "component: ";
for (int u:tmp)
cout << u << ' ';
cout << '\n';*/
}
int sz=components.size(), loog=log2(sz-0.5), ind=0;
for (int j=loog; j; j--)
{
vector<int> vec1, vec0;
for (int k=0; k<sz; k++)
{
if (k&(1<<j))
{
for (int u:components[k])
vec1.push_back(u);
}
else
{
for (int u:components[k])
vec0.push_back(u);
}
}
int a[vec1.size()], b[vec0.size()];
for (int k=0; k<vec1.size(); k++)
a[k]=vec1[k];
for (int k=0; k<vec0.size(); k++)
b[k]=vec0[k];
int res=query(vec1.size(), vec0.size(), a, b);
if (res)
{
ind=j;
break;
}
}
int l=0, r=(sz-1)/(1<<(ind+1));
while (l<r)
{
int mid=(l+r)/2;
vector<int> vec1, vec0;
for (int j=(1<<(ind+1))*l; j<min(sz, (1<<(ind+1))*(mid+1)); j++)
{
if (j&(1<<ind))
{
for (int u:components[j])
vec1.push_back(u);
}
else
{
for (int u:components[j])
vec0.push_back(u);
}
}
int a[vec1.size()], b[vec0.size()];
for (int k=0; k<vec1.size(); k++)
a[k]=vec1[k];
for (int k=0; k<vec0.size(); k++)
b[k]=vec0[k];
int res=query(vec1.size(), vec0.size(), a, b);
if (res)
r=mid;
else
l=mid+1;
}
vector<int> vec1, vec0;
for (int j=(1<<(ind+1))*l; j<min(sz, (1<<(ind+1))*(l+1)); j++)
{
if (j&(1<<ind))
{
for (int u:components[j])
vec1.push_back(u);
}
else
{
for (int u:components[j])
vec0.push_back(u);
}
}
/*cout << "edge must be between ";
for (int u:vec1)
cout << u << ' ';
cout << "and ";
for (int v:vec0)
cout << v << ' ';
cout << '\n';*/
int ll=0, rr=vec1.size()-1;
while (ll<rr)
{
int mid=(ll+rr)/2;
int a[mid-ll+1], b[vec0.size()];
for (int k=ll; k<=mid; k++)
a[k-ll]=vec1[k];
for (int k=0; k<vec0.size(); k++)
b[k]=vec0[k];
int res=query(mid-ll+1, vec0.size(), a, b);
if (res)
rr=mid;
else
ll=mid+1;
}
int lll=0, rrr=vec0.size()-1;
while (lll<rrr)
{
int mid=(lll+rrr)/2;
int a[1]={vec1[ll]}, b[mid-lll+1];
for (int k=lll; k<=mid; k++)
b[k-lll]=vec0[k];
int res=query(1, mid-lll+1, a, b);
if (res)
rrr=mid;
else
lll=mid+1;
}
int U=vec1[ll], V=vec0[lll];
adj[U].push_back(V);
adj[V].push_back(U);
setRoad(U, V);
}
}
