#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 1001;
bool vis[N], ans[N];
int c[N];
vector<int> adj[N], v[2];
bool ban[N][3];
} // namespace
void dfs(int u) {
vis[u] = true;
v[c[u]].push_back(u);
for (int v : adj[u]) if (!vis[v]) {
c[v] = c[u] ^ 1;
dfs(v);
}
}
void helper(int a, int b) {
if (ans[a] || ans[b]) return;
ans[a] = ans[b] = true;
Answer(a, b);
}
void Solve(int n) {
for (int i = 2; i <= 2 * n; i++) {
for (int j = 1; j <= i; j++) vis[j] = false;
v[0].clear(); v[1].clear();
for (int j = 1; j < i; j++) if (!vis[j]) dfs(j);
for (int j = 0; j < 2; j++) {
while (true) {
vector<int> q = v[j];
q.push_back(i);
int res = Query(q);
if (res < q.size()) {
int l = 0, r = v[j].size() - 1;
while (l < r) {
q.clear();
int mid = (l + r) / 2;
for (int k = 0; k <= mid; k++) q.push_back(v[j][k]);
q.push_back(i);
res = Query(q);
if (res < q.size()) r = mid;
else l = mid + 1;
}
adj[v[j][l]].push_back(i);
adj[i].push_back(v[j][l]);
v[j].erase(v[j].begin() + l);
} else break;
}
}
}
for (int i = 1; i <= 2 * n; i++) {
if (ans[i]) continue;
if ((int) adj[i].size() == 1) helper(i, adj[i][0]);
if (ans[i]) continue;
int r01 = Query({i, adj[i][0], adj[i][1]});
int r12 = Query({i, adj[i][1], adj[i][2]});
int loves;
if (r01 == 2 && r12 == 2) loves = 1;
else if (r01 == 2 && r12 == 1) loves = 0;
else loves = 2;
ban[i][loves] = true;
int x = adj[i][loves];
for (int j = 0; j < 3; j++) {
if (adj[x][j] == i) ban[x][j] = true;
}
}
for (int i = 1; i <= 2 * n; i++) {
if (ans[i]) continue;
int cnt = 0, idx = 0;
for (int j = 0; j < adj[i].size(); j++) if (!ban[i][j]) cnt++, idx = j;
helper(i, adj[i][idx]);
}
}
