#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int n;
int tata[105];
int dim[105];
int roots[105];
vector<int> nodes[105];
int incercat[105];
int a[105];
int b[105];
int temp[105];
int dir[105];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rad(int x)
{
if(x == tata[x])
{
return x;
}
int r = rad(tata[x]);
tata[x] = r;
return r;
}
void unire(int x, int y)
{
int rx = rad(x);
int ry = rad(y);
if(rx == ry)
{
exit(1);
}
if(dim[ry] > dim[rx])
{
swap(rx, ry);
}
tata[ry] = rx;
dim[rx] += dim[ry];
}
int ask_components(int st, int mij1, int mij2, int dr)
{
int inda = 0;
int indb = 0;
for(int i = st; i<=mij1; i++)
{
for(auto it: nodes[roots[i]])
{
a[inda] = it;
inda++;
}
}
for(int i = mij2; i<=dr; i++)
{
for(auto it: nodes[roots[i]])
{
b[indb] = it;
indb++;
}
}
return query(inda, indb, a, b);
}
int ask_nodes(int st, int mij1, int mij2, int dr)
{
int inda = 0;
int indb = 0;
for(int i = st; i<=mij1; i++)
{
a[inda] = temp[i];
inda++;
}
for(int i = mij2; i<=dr; i++)
{
b[indb] = temp[i];
indb++;
}
return query(inda, indb, a, b);
}
pair<int, int> find_edge()
{
for(int i = 1; i<=n; i++)
{
nodes[i].clear();
incercat[i] = 0;
}
int cnt = 0;
for(int i = 1; i<=n; i++)
{
if(i == rad(i))
{
cnt++;
roots[cnt] = i;
}
nodes[rad(i)].push_back(i);
}
int poz = -1;
while(1)
{
int inda = 0;
int indb = 0;
for(int i = 1; i<=cnt; i++)
{
int x = uniform_int_distribution<int>(0, 1)(rng);
if(x == 0)
{
dir[i] = 1;
for(auto it: nodes[roots[i]])
{
a[inda] = it;
inda++;
}
}
else
{
dir[i] = 2;
for(auto it: nodes[roots[i]])
{
b[indb] = it;
indb++;
}
}
}
if(query(inda, indb, a, b) == 1)
{
int ind = 0;
for(int i = 1; i<=cnt; i++)
{
if(dir[i] == 1)
{
ind++;
temp[ind] = roots[i];
}
}
poz = ind;
for(int i = 1; i<=cnt; i++)
{
if(dir[i] == 2)
{
ind++;
temp[ind] = roots[i];
}
}
for(int i = 1; i<=cnt; i++)
{
roots[i] = temp[i];
}
break;
}
}
if(poz == -1)
{
exit(1);
}
int st = 1;
int dr = poz;
int left = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(ask_components(mij, poz, poz + 1, cnt) == 1)
{
left = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
st = poz + 1;
dr = cnt;
int right = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(ask_components(1, poz, poz + 1, mij) == 1)
{
right = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
if(left == -1 || right == -1)
{
exit(1);
}
int ind = 0;
for(auto it: nodes[roots[left]])
{
ind++;
temp[ind] = it;
}
poz = ind;
for(auto it: nodes[roots[right]])
{
ind++;
temp[ind] = it;
}
st = 1;
dr = poz;
int left_nod = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(ask_nodes(mij, poz, poz + 1, ind) == 1)
{
left_nod = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
st = poz + 1;
dr = ind;
int right_nod = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(ask_nodes(1, poz, poz + 1, mij) == 1)
{
right_nod = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
if(left_nod == -1 || right_nod == -1)
{
exit(1);
}
return {temp[left_nod], temp[right_nod]};
}
void run(int N)
{
n = N;
for(int i = 1; i<=n; i++)
{
tata[i] = i;
dim[i] = 1;
}
for(int i = 1; i<n; i++)
{
pair<int, int> muc = find_edge();
unire(muc.first, muc.second);
setRoad(muc.first, muc.second);
}
}
//int main()
//{
// cout << "Hello world!" << endl;
// return 0;
//}
