#define db(...) fprintf(stderr, __VA_ARGS__)
#include "icc.h"
#include <cstdio>
#include <random>
#include <chrono>
#include <algorithm>
#include <vector>
#include <cstring>
#define X first
#define Y second
#define PB push_back
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef pair<int, int> pii;
const int N = 110;
int n, un[N];
int trazi(int u) { return un[u] == u ? u : un[u] = trazi(un[u]); }
void unija(int u, int v) {
u = trazi(u);
v = trazi(v);
un[u] = v;
}
void include(int u, vector<int> &v) {
for(int i = 1; i <= n; ++i) {
if(trazi(i) == u) { v.PB(i); }
}
}
bool _query(vector<int> &a, vector<int> &b) {
int s = a.size(), s_ = b.size();
int x[s], y[s_];
for(int i = 0; i < s; ++i) { x[i] = a[i]; }
for(int i = 0; i < s_; ++i) { y[i] = b[i]; }
return query(s, s_, x, y);
}
bool __query(vector<vector<int>> &a, vector<vector<int>> &b) {
vector<int> A, B;
for(auto &i : a) {
for(int x : i) { include(x, A); }
}
for(auto &i : b) {
for(int x : i) { include(x, B); }
}
return _query(A, B);
}
void debug(vector<int> &v, const char c[]) {
for(int x : v) db("%d ", x);
db("%s", c);
}
void findhalf(vector<int> &a, vector<int> &b, vector<int> u) {
vector<vector<int>> A, B;
A.PB({});
B.PB({});
for(int i = 0; i < (int) u.size(); ++i) {
if(i < (int) u.size() / 2) { A[0].PB(u[i]); }
else { B[0].PB(u[i]); }
}
for(; !__query(A, B); ) {
if(A.empty() && B.empty()) { exit(0); }
// for(auto &i : A) debug(i, "");
// db("| ");
// for(auto &i : B) debug(i, "");
// db("\n");
vector<vector<int>> A_, B_;
for(auto &i : A) {
if((int) i.size() <= 1) { continue; }
vector<int> a, b;
for(int j = 0; j < (int) i.size(); ++j) {
if(j < (int) i.size() / 2) { a.PB(i[j]); }
else { b.PB(i[j]); }
}
A_.PB(a);
B_.PB(b);
}
for(auto &i : B) {
if((int) i.size() <= 1) { continue; }
vector<int> a, b;
for(int j = 0; j < (int) i.size(); ++j) {
if(j < (int) i.size() / 2) { a.PB(i[j]); }
else { b.PB(i[j]); }
}
A_.PB(a);
B_.PB(b);
}
A = A_;
B = B_;
}
for(auto &i : A) { for(int x : i) { a.PB(x); } }
for(auto &i : B) { for(int x : i) { b.PB(x); } }
}
int binsearch(vector<int> &a, vector<int> &b) {
int lo = -1, hi = (int) a.size() - 1;
for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) {
vector<int> a_;
for(int i = 0; i <= mi; ++i) { a_.PB(a[i]); }
if(_query(a_, b)) { hi = mi; }
else { lo = mi; }
}
return a[hi];
}
void run(int nn) {
n = nn;
for(int i = 1; i <= n; ++i) { un[i] = i; }
for(int ii = 0; ii < n - 1; ++ii) {
vector<int> u, a, b;
for(int i = 1; i <= n; ++i) {
if(trazi(i) == i) { u.PB(i); }
}
debug(u, "unions\n");
findhalf(a, b, u);
vector<int> A, B;
for(int i : a) { include(i, A); }
for(int i : b) { include(i, B); }
debug(A, "A\n");
debug(B, "B\n");
int x = binsearch(A, B);
int y = binsearch(B, A);
db(">>> %d - %d <<<\n", x, y);
setRoad(x, y);
unija(x, y);
}
return;
}
