#include "bits/stdc++.h"
#include "icc.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 100;
int a[N], b[N], cur[N];
void clear() {
for (int i = 0; i < N; i++) {
a[i] = 0, b[i] = 0;
}
}
void clear_cur() {
for (int i = 0; i < N; i++)
cur[i] = 0;
}
void run(int n) {
vector<vector<int>> cmp(n);
for (int i = 0; i < n; i++)
cmp[i].push_back(i + 1);
for (int _ = 0; _ < n - 1; _++) {
int k = sz(cmp);
vector<pii> intervals = {{0, k - 1}};
vector<pii> nxt;
while (1) {
for (auto [l, r] : intervals) {
if (l == r) {
nxt.push_back({l, r});
continue;
}
int m = (l + r) / 2;
nxt.push_back({l, m});
nxt.push_back({m + 1, r});
}
swap(intervals, nxt);
clear();
int size_a = 0;
for (int i = 0; i < sz(intervals); i += 2) {
auto [l, r] = intervals[i];
for (int j = l; j <= r; j++)
for (int x : cmp[j])
a[size_a++] = x;
}
int size_b = 0;
for (int i = 1; i < sz(intervals); i += 2) {
auto [l, r] = intervals[i];
for (int j = l; j <= r; j++)
for (int x : cmp[j])
b[size_b++] = x;
}
if (query(size_a, size_b, a, b) == 1) {
auto recA = [&](auto recA, int l, int r) -> int {
if (l == r) return a[l];
int m = (l + r) / 2;
clear_cur();
int size = 0;
for (int i = l; i <= m; i++)
cur[size++] = a[i];
if (query(size, size_b, cur, b) == 1)
return recA(recA, l, m);
else
return recA(recA, m + 1, r);
};
auto recB = [&](auto recB, int l, int r) -> int {
if (l == r) return b[l];
int m = (l + r) / 2;
clear_cur();
int size = 0;
for (int i = l; i <= m; i++)
cur[size++] = b[i];
if (query(size, size_a, cur, a) == 1)
return recB(recB, l, m);
else
return recB(recB, m + 1, r);
};
int A = recA(recA, 0, size_a - 1);
int B = recB(recB, 0, size_b - 1);
setRoad(A, B);
vector<vector<int>> nxt_cmp;
int id = -1;
for (int i = 0; i < k; i++) {
bool f = false;
for (int x : cmp[i])
if (x == A || x == B)
f = true;
if (!f) {
nxt_cmp.push_back(cmp[i]);
} else {
if (id == -1) {
id = i;
nxt_cmp.push_back(cmp[i]);
} else {
for (int x : cmp[i])
nxt_cmp[id].push_back(x);
}
}
}
swap(cmp, nxt_cmp);
break;
}
}
}
}
