#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
const int NMAX = 100;
mt19937 mt(1725435865);
int A[NMAX], B[NMAX];
int cnt1, cnt2;
int cmp[NMAX + 1];
vector<vector<int>> comp;
void run(int n) {
comp.resize(n);
for (int i = 0; i < n; i++)
comp[i].push_back(i + 1);
int nrc = n;
for (int step = 1; step < n; step++) {
vector<int> perm(nrc);
iota(perm.begin(), perm.end(), 0);
bool diffHalfs = false;
while (!diffHalfs) {
shuffle(perm.begin(), perm.end(), mt);
cnt1 = cnt2 = 0;
for (int i = 0; i < nrc / 2; i++) {
for (int node : comp[perm[i]]) {
cmp[node] = perm[i];
A[cnt1++] = node;
}
}
for (int i = nrc / 2; i < nrc; i++) {
for (int node : comp[perm[i]]) {
cmp[node] = perm[i];
B[cnt2++] = node;
}
}
diffHalfs = query(cnt1, cnt2, A, B);
}
int pos1, pos2;
pos1 = cnt1 - 1;
pos2 = cnt2 - 1;
int st = 0;
int dr = cnt1 - 2;
while (st <= dr) {
int mij = (st + dr) / 2;
if (query(mij + 1, cnt2, A, B)) {
pos1 = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
st = 0;
dr = cnt2 - 2;
while (st <= dr) {
int mij = (st + dr) / 2;
if (query(cnt1, mij + 1, A, B)) {
pos2 = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
setRoad(A[pos1], B[pos2]);
pos1 = cmp[A[pos1]];
pos2 = cmp[B[pos2]];
if (pos1 > pos2) swap(pos1, pos2);
for (int node : comp[pos2])
comp[pos1].push_back(node);
for (int i = pos2; i + 1 < nrc; i++)
comp[i] = comp[i + 1];
nrc--;
}
}
