#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef long long ll;
const int N_MAX = 100;
vector <int> adj[N_MAX + 2];
vector <int> component[N_MAX + 2];
bool visited[N_MAX + 2];
int cntComp = 0;
void dfs(int u) {
visited[u] = true;
component[cntComp].push_back(u);
for (int v : adj[u]) {
if (visited[v] == false) {
dfs(v);
}
}
}
int A[N_MAX + 2], B[N_MAX + 2];
void run(int N) {
for (int t = 1; t < N; t++) {
int U = 0, V = 0;
for (int i = 1; i <= N; i++) {
visited[i] = false;
}
for (int i = 1; i <= N; i++) {
if (visited[i] == 0) {
cntComp++;
dfs(i);
}
}
int cntA = 0, cntB = 0;
for (int bit = 0; bit < 7; bit++) {
cntA = 0;
cntB = 0;
for (int i = 1; i <= cntComp; i++) {
if ((i >> bit) & 1) {
for (int j : component[i]) {
A[cntA++] = j;
}
} else {
for (int j : component[i]) {
B[cntB++] = j;
}
}
}
if (query(cntA, cntB, A, B) == true) {
break;
}
}
int l = 0, r = cntA - 1;
while (l < r) {
int mid = (l + r) / 2;
if (query(mid - l + 1, cntB, A + l, B) == true) {
r = mid;
} else {
l = mid + 1;
}
}
U = A[l];
l = 0;
r = cntB - 1;
while (l < r) {
int mid = (l + r) / 2;
if (query(cntA, mid - l + 1, A, B + l) == true) {
r = mid;
} else {
l = mid + 1;
}
}
V = B[l];
setRoad(U, V);
adj[U].push_back(V);
adj[V].push_back(U);
for (int i = 1; i <= cntComp; i++) {
component[i].clear();
}
cntComp = 0;
}
}
