#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int s, vector<set<int>> const &adj, vector<int> &a, vector<int> &b,
vector<bool> &vis, bool flag) {
if (vis[s])
return;
vis[s] = true;
if (flag)
b.push_back(s);
else
a.push_back(s);
for (auto &x : adj[s]) {
if (vis[x])
continue;
dfs(x, adj, a, b, vis, (flag xor true));
}
}
void bipartite(vector<set<int>> const &adj, vector<int> &a, vector<int> &b,
int ind) {
vector<bool> vis(ind, false);
for (int i = 0; i < ind; i++) {
if (!vis[i])
dfs(i, adj, a, b, vis, false);
}
}
void Solve(int N) {
vector<set<int>> adj(N << 1);
for (int i = 0; i < (N << 1); i++) {
vector<int> a, b;
bipartite(adj, a, b, i);
int l = 0, r = a.size() - 1;
int ll = 0;
int ans = INT_MAX;
while (true) {
vector<int> totest = {i + 1};
for (int i = ll; i < a.size(); i++)
totest.emplace_back(a[i] + 1);
int test = Query(totest);
if (test == totest.size())
break;
while (l <= r) {
int m = (l + r) >> 1;
vector<int> toans = {i + 1};
for (int j = ll; j <= m; j++)
toans.push_back(a[j] + 1);
int ret = Query(toans);
if (ret != toans.size()) {
ans = min(ans, m);
r = m - 1;
} else {
l = m + 1;
}
}
adj[i].insert(a[ans]);
adj[a[ans]].insert(i);
l = ans + 1;
ll = ans + 1;
r = a.size() - 1;
ans = INT_MAX;
}
l = 0, r = b.size() - 1;
ll = 0;
ans = INT_MAX;
while (true) {
vector<int> totest = {i + 1};
for (int i = ll; i < b.size(); i++)
totest.emplace_back(b[i] + 1);
int test = Query(totest);
if (test == totest.size())
break;
while (l <= r) {
int m = (l + r) >> 1;
vector<int> toans = {i + 1};
for (int j = ll; j <= m; j++)
toans.push_back(b[j] + 1);
int ret = Query(toans);
if (ret != toans.size()) {
ans = min(ans, m);
r = m - 1;
} else {
l = m + 1;
}
}
adj[i].insert(b[ans]);
adj[b[ans]].insert(i);
l = ans + 1;
ll = ans + 1;
r = b.size() - 1;
ans = INT_MAX;
}
}
vector<pair<int, int>> toign;
for (int i = 0; i < (N << 1); i++) {
if (adj[i].empty() || adj[i].size() == 1) {
continue;
} else {
vector<int> tmp;
for (auto x : adj[i])
tmp.push_back(x);
for (int k = 0; k < 3; k++) {
vector<int> toask = {i + 1};
for (int j = 0; j < 3; j++)
if (j != k)
toask.push_back(tmp[j] + 1);
int ans = Query(toask);
if (ans == 1) {
toign.emplace_back(i, tmp[k]);
break;
}
}
}
}
for (auto &[x, y] : toign) {
adj[x].erase(y);
adj[y].erase(x);
}
for (int i = 0; i < (N << 1); i++) {
if (adj[i].empty())
continue;
else {
Answer(i + 1, (*adj[i].begin()) + 1);
adj[*adj[i].begin()].clear();
adj[i].clear();
}
}
}
