#include "chameleon.h"
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../debug.h"
#else
#define debug(...) void(23)
#endif
namespace {
// int variable_example = 1;
std::vector<int> mtc;
} // namespace
void answer(int a, int b) {
debug("answer:", a, b);
if (mtc[a] != -1) {
assert(mtc[a] == b);
} else {
mtc[a] = b;
mtc[b] = a;
Answer(a + 1, b + 1);
}
}
int query(std::vector<int> v) {
for (auto& i : v) {
i += 1;
}
return Query(v);
}
void Solve(int N) {
// std::vector<int> p(3);
// p[0] = 1;
// p[1] = 2;
// p[2] = 3;
// variable_example = Query(p);
// for (int i = 0; i < N; ++i) {
// Answer(i * 2 + 1, i * 2 + 2);
// }
std::vector<std::vector<int>> adj(2 * N);
std::vector<int> col;
auto dfs = [&](auto&& self, int v) -> void {
for (auto u : adj[v]) {
if (col[u] == -1) {
col[u] = !col[v];
self(self, u);
} else {
assert(col[u] == !col[v]);
}
}
};
for (int i = 0; i < 2 * N; ++i) {
col.assign(2 * N, -1);
std::vector<int> gr[2];
for (int j = 0; j < i; ++j) {
if (col[j] == -1) {
col[j] = 0;
dfs(dfs, j);
}
gr[col[j]].emplace_back(j);
}
debug(i);
debug(gr[0]);
debug(gr[1]);
for (int g : {0, 1}) {
std::vector<int> all = gr[g];
while (int(adj[i].size()) != 3) {
auto v = all;
v.emplace_back(i);
if (query(v) == int(v.size())) {
break;
}
v.pop_back();
while (int(v.size()) > 1) {
int n = int(v.size());
std::vector<int> vl(v.begin(), v.begin() + n / 2);
std::vector<int> vr(v.begin() + n / 2, v.end());
vl.emplace_back(i);
if (query(vl) != n / 2 + 1) {
vl.pop_back();
v = vl;
} else {
v = vr;
}
}
debug(v[0], i);
adj[v[0]].emplace_back(i);
adj[i].emplace_back(v[0]);
all.erase(std::find(all.begin(), all.end(), v[0]));
}
}
}
for (int i = 0; i < 2 * N; ++i) {
debug(i, adj[i]);
}
mtc.assign(2 * N, -1);
for (int i = 0; i < 2 * N; ++i) {
if (adj[i].size() == 1) {
int x = adj[i][0];
answer(i, x);
}
}
std::vector<std::pair<int, int>> err;
for (int i = 0; i < 2 * N; ++i) {
if (int(adj[i].size()) == 3) {
int a = adj[i][0];
int b = adj[i][1];
int c = adj[i][2];
int x = query({i, a, b});
int y = query({i, a, c});
int z = query({i, b, c});
if (x == 1) {
err.emplace_back(i, c);
} else if (y == 1) {
err.emplace_back(i, b);
} else {
err.emplace_back(i, a);
}
}
}
for (auto[x, y] : err) {
debug(x, y);
auto itx = std::find(adj[x].begin(), adj[x].end(), y);
auto ity = std::find(adj[y].begin(), adj[y].end(), x);
if (itx != adj[x].end()) {
adj[x].erase(itx);
}
if (ity != adj[y].end()) {
adj[y].erase(ity);
}
}
for (int i = 0; i < 2 * N; ++i) {
debug(adj[i]);
}
for (int i = 0; i < 2 * N; ++i) {
if (!adj[i].empty()) {
answer(i, adj[i][0]);
}
}
}
