#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);
}
void debug(vector<int> &v, const char c[]) {
db("%s ", c);
for(int x : v) db("%d ", x);
db("\n");
}
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");
for(; 1; ) {
shuffle(u.begin(), u.end(), rng);
a.clear();
b.clear();
for(int i = 0; i < (int) u.size(); ++i) {
if(i < (int) u.size() / 2) { a.PB(u[i]); }
else { b.PB(u[i]); }
}
vector<int> A, B;
for(int i : a) { include(i, A); }
for(int i : b) { include(i, B); }
if(_query(A, B)) { break; }
}
vector<int> A, B;
for(int i : a) { include(i, A); }
for(int i : b) { include(i, B); }
debug(A, "A");
debug(B, "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; }
}
int ans = A[hi];
lo = -1;
hi = B.size() - 1;
for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) {
vector<int> B_;
for(int i = 0; i <= mi; ++i) { B_.PB(B[i]); }
if(_query(A, B_)) { hi = mi; }
else { lo = mi; }
}
db(">>> %d - %d <<<\n", ans, B[hi]);
setRoad(ans, B[hi]);
unija(ans, B[hi]);
}
return;
}
