#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
const int N = 105;
int par[N];
vector<int> vec[N];
int find(int u) {
return (u == par[u]) ? u : par[u] = find(par[u]);
}
void join(int u, int v) {
u = find(u), v = find(v);
if (vec[u].size() > vec[v].size()) swap(u, v);
for (auto i : vec[u]) vec[v].push_back(i);
par[u] = v, vec[u].clear();
}
bool query(vector<int> a, vector<int> b) {
int sza = a.size(), szb = b.size();
int A[N], B[N];
for (int i = 0; i < sza; ++i) A[i] = a[i];
for (int i = 0; i < szb; ++i) B[i] = b[i];
return query(sza, szb, A, B);
}
void find(int l, int r, vector<int> &go, vector<int> &to) {
if (l == r) {
int tmp = go[l]; go.clear(); go.push_back(tmp); return;
}
int mid = (l + r) >> 1;
vector<int> a, b; b = to;
for (int i = l; i <= mid; ++i) a.push_back(go[i]);
if (query(a, b)) find(l, mid, go, to);
else find(mid + 1, r, go, to);
}
void cal(vector<int> vx, vector<int> vy) {
find(0, vx.size() - 1, vx, vy);
find(0, vy.size() - 1, vy, vx);
setRoad(vx[0], vy[0]), join(vx[0], vy[0]);
}
void run(int n) {
for (int i = 1; i <= n; ++i) par[i] = i, vec[i].push_back(i);
while (1) {
vector<int> go;
for (int i = 1; i <= n; ++i) {
if (find(i) == i) go.push_back(i);
}
int sz = go.size();
for (int i = 0; (1 << i) < sz; ++i) {
vector<int> a, b;
for (int j = 0; j < sz; ++j) {
if (j >> i & 1) {
for (auto k : vec[go[j]]) a.push_back(k);
}
else {
for (auto k : vec[go[j]]) b.push_back(k);
}
}
if (query(a, b)) {
cal(a, b); break;
}
}
}
}
