#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << x << endl;
#define displaya(a, st, n)\
{cerr << #a << " = {";\
for(int qwq = (st); qwq <= (n); ++qwq) {\
if(qwq == (st)) cerr << a[qwq];\
else cerr << ", " << a[qwq];\
} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
return out << '(' << p.first << ", " << p.second << ')';
}
namespace {
const int maxN = 500 * 2 + 5;
int n;
set<int> G[maxN];
vector<int> fam[maxN][2];
int pa[maxN], side[maxN];
} // namespace
void merge(int x, int y) {
int t = side[x] ^ side[y] ^ 1;
fam[pa[x]][0].insert(fam[pa[x]][0].end(), fam[pa[y]][t].begin(), fam[pa[y]][t].end());
fam[pa[x]][1].insert(fam[pa[x]][1].end(), fam[pa[y]][1^t].begin(), fam[pa[y]][1^t].end());
int py = pa[y];
for(int u : fam[py][0]) pa[u] = pa[x], side[u] ^= t;
for(int u : fam[py][1]) pa[u] = pa[x], side[u] ^= t;
fam[py][0].clear(); fam[py][1].clear();
}
void link(int x, int y) {
eprintf("%d %d\n", x, y);
if(pa[x] != pa[y]) merge(x, y);
else assert(side[x] != side[y]);
G[x].insert(y);
G[y].insert(x);
}
void getadj(int u, vector<int> all) {
display(u); displayv(all);
all.insert(all.begin(), u);
while(Query(all) != all.size()) {
int L = 1, R = (int)all.size() - 1;
while(L < R) {
int M = (L + R) / 2;
vector<int> q(all.begin(), all.begin() + M + 1);
if(Query(q) != q.size()) R = M;
else L = M + 1;
}
link(all[0], all[L]);
all.erase(all.begin() + 1, all.begin() + L + 1);
}
}
void Solve(int n) {
::n = n;
for(int i = 1; i <= 2 * n; ++i) {
pa[i] = i; side[i] = 0; fam[i][0].push_back(i);
vector<int> x, y;
for(int j = 1; j < i; ++j) if(pa[j] == j) {
x.insert(x.end(), fam[j][0].begin(), fam[j][0].end());
y.insert(y.end(), fam[j][1].begin(), fam[j][1].end());
}
getadj(i, x);
getadj(i, y);
}
int sd = 0;
for(int i = 1; i <= 2 * n; ++i) sd += side[i];
assert(sd == n);
for(int i = 1; i <= 2 * n; ++i) assert(G[i].size() == 1 || G[i].size() == 3);
vector<pii> rem;
for(int i = 1; i <= 2 * n; ++i) if(G[i].size() == 3) {
int x = *G[i].begin(), y = *next(G[i].begin()), z = *next(next(G[i].begin()));
if(Query({i, x, y}) == 1) rem.emplace_back(i, z);
else if(Query({i, x, z}) == 1) rem.emplace_back(i, y);
else if(Query({i, y, z}) == 1) rem.emplace_back(i, x);
else assert(false);
}
displayv(rem);
for(auto p : rem)
G[p.first].erase(p.second),
G[p.second].erase(p.first);
for(int i = 1; i <= 2 * n; ++i) {
assert(G[i].size() == 1);
if(*G[i].begin() > i) Answer(i, *G[i].begin());
}
}
