#include <bits/stdc++.h>
#include "chameleon.h"
template <class T>
using Vec = std::vector<T>;
template <class F>
struct RecLambda: private F {
explicit RecLambda(F &&f): F(std::forward<F>(f)) { }
template <class... Args>
decltype(auto) operator () (Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
void Solve(int N) {
Vec<int> color(2 * N + 1);
Vec<Vec<int>> graph(2 * N + 1);
const auto difference = [&](const int src, Vec<int> vec) {
vec.push_back(src);
return (int) vec.size() - Query(vec);
};
const auto enum_edges = RecLambda([&](const auto enum_edges, const int src, Vec<int> partner, int dif) -> int {
if (graph[src].size() == 3) {
return 0;
}
if (dif == -1) {
dif = difference(src, partner);
}
if (dif == 0) {
return 0;
}
if (partner.size() == 1) {
return partner.front();
}
const auto mid = (int) partner.size() / 2;
Vec<int> left(partner.begin(), partner.begin() + mid);
Vec<int> right(partner.begin() + mid, partner.end());
const auto left_dif = difference(src, left);
if (left_dif == 0) {
return enum_edges(src, right, dif);
}
else {
return enum_edges(src, left, left_dif);
}
});
const auto split = RecLambda([&](const auto split, const int u, const int c) -> void {
if (color[u] != 0) {
return;
}
color[u] = c;
for (const auto v: graph[u]) {
split(v, -c);
}
});
for (int src = 1; src <= 2 * N; ++src) {
Vec<int> v1, v2;
for (int v = 1; v < src; ++v) {
bool ok = true;
for (const auto x: graph[src]) {
if (x == v) {
ok = false;
break;
}
}
if (ok) {
(color[v] == 1 ? v1 : v2).push_back(v);
}
}
while (true) {
const auto dst = enum_edges(src, v1, -1);
if (dst == 0) {
break;
}
v1.erase(std::lower_bound(v1.begin(), v1.end(), dst));
graph[src].push_back(dst);
graph[dst].push_back(src);
}
while (true) {
const auto dst = enum_edges(src, v2, -1);
if (dst == 0) {
break;
}
v2.erase(std::lower_bound(v2.begin(), v2.end(), dst));
graph[src].push_back(dst);
graph[dst].push_back(src);
}
std::fill(color.begin(), color.end(), 0);
for (int v = 1; v <= src; ++v) {
if (color[v] == 0) {
split(v, 1);
}
}
}
std::set<std::pair<int, int>> good;
const auto add_good = [&](const int src, const int dst) {
if (good.find(std::make_pair(dst, src)) != good.end()) {
Answer(src, dst);
}
good.emplace(src, dst);
};
for (int src = 1; src <= 2 * N; ++src) {
if (graph[src].size() == 1) {
add_good(src, graph[src].front());
}
else {
for (int ng = 0; ng < 3; ++ng) {
const auto check = graph[src][ng];
Vec<int> ask;
for (const auto dst: graph[src]) {
if (check != dst) {
ask.push_back(dst);
}
}
if (difference(src, ask) == 1) {
add_good(src, check);
}
}
}
}
}
