#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
int ask(vector<int> a, vector<int> b) {
for (int &x : a) ++x;
for (int &y : b) ++y;
return query(sz(a), sz(b), a.data(), b.data());
}
vector<int> p;
int get(int a) {
return a == p[a] ? a : p[a] = get(p[a]);
}
bool mrg(int a, int b) {
a = get(a), b = get(b);
if (a == b) {
return false;
}
p[b] = a;
return true;
}
void run(int n) {
p.resize(n);
iota(all(p), 0);
for (int cnt = 1; cnt < n; ++cnt) {
vector<int> v;
for (int i = 0; i < n; ++i) {
if (p[i] == i) v.push_back(i);
}
assert(sz(p) > 1);
vector<vector<int>> f, s;
f.emplace_back(), s.emplace_back();
for (int i = 0; i < sz(v); ++i) {
if (i & 1) s.back().push_back(v[i]);
else f.back().push_back(v[i]);
}
while (true) {
vector<int> a, b;
for (auto &x: f) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) a.push_back(i);
}
}
}
for (auto &x: s) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) b.push_back(i);
}
}
}
if (ask(a, b)) break;
vector<vector<int>> ff, ss;
for (auto &x: f) {
ff.emplace_back();
ss.emplace_back();
for (int i = 0; i < sz(x); ++i) {
if (i & 1) ss.back().push_back(x[i]);
else ff.back().push_back(x[i]);
}
if (ss.back().empty()) ss.pop_back();
if (ff.back().empty()) ff.pop_back();
}
for (auto &x: s) {
ff.emplace_back();
ss.emplace_back();
for (int i = 0; i < sz(x); ++i) {
if (i & 1) ss.back().push_back(x[i]);
else ff.back().push_back(x[i]);
}
if (ss.back().empty()) ss.pop_back();
if (ff.back().empty()) ff.pop_back();
}
swap(f, ff);
swap(s, ss);
}
{
vector<int> a, b;
for (auto &x: f) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) a.push_back(i);
}
}
}
for (auto &x: s) {
for (int y: x) {
for (int i = 0; i < n; ++i) {
if (get(i) == y) b.push_back(i);
}
}
}
int l = 0, r = sz(b);
while (l + 1 < r) {
int m = (l + r) >> 1;
vector<int> c;
for (int i = l; i < m; ++i) {
c.push_back(b[i]);
}
if (ask(a, c)) r = m;
else l = m;
}
int v1 = b[l];
l = 0, r = sz(a);
while (l + 1 < r) {
int m = (l + r) >> 1;
vector<int> c;
for (int i = l; i < m; ++i) {
c.push_back(a[i]);
}
if (ask({v1}, c)) r = m;
else l = m;
}
int v2 = a[l];
setRoad(v1 + 1, v2 + 1);
mrg(v1, v2);
}
}
}
