#include "minerals.h"
#include "bits/stdc++.h"
using i64 = long long;
#ifdef DEBUG
#include "../debug.h"
#else
#define debug(...) void(23)
#endif
namespace {
std::random_device rd;
std::mt19937 rng(rd());
int N;
std::vector<int> p;
std::vector<int> color;
int lst1 = 0, lst2 = 0;
std::set<int> inside;
void flip(int x) {
if (inside.count(x)) {
inside.erase(x);
} else {
inside.emplace(x);
}
int res = Query(p[x]);
lst2 = lst1;
lst1 = res;
}
void dnq(std::set<int> s0, std::set<int> s1) {
debug(s0, s1);
assert(s0.size() == s1.size());
if (s0.size() == 1) {
Answer(p[*s0.begin()], p[*s1.begin()]);
return;
}
std::vector<int> v0(s0.begin(), s0.end());
std::vector<int> v1(s1.begin(), s1.end());
int n = int(v0.size());
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += inside.count(v0[i]);
}
assert(cnt == 0 || cnt == n);
int xr = (cnt == 0 ? 0 : 1);
int m = std::max<int>(1, 0.38 * n);
for (int i = 0; i < m; ++i) {
flip(v0[i]);
}
std::set<int> s[2];
for (int i = 0; i < n; ++i) {
if (s[0].size() == m) {
s[1].emplace(v1[i]);
} else if (s[1].size() == n - m) {
s[0].emplace(v1[i]);
} else {
flip(v1[i]);
s[(lst1 != lst2) ^ xr].emplace(v1[i]);
}
}
dnq(std::set(v0.begin(), v0.begin() + m), s[0]);
dnq(std::set(v0.begin() + m, v0.end()), s[1]);
}
};
void Solve(int N) {
::N = N;
p.resize(2 * N);
std::iota(p.begin(), p.end(), 1);
std::shuffle(p.begin(), p.end(), rng);
debug(p);
color.resize(2 * N);
int cnt0 = 0;
std::set<int> s[2];
for (int i = 0; i < 2 * N; ++i) {
if (cnt0 == N) {
color[i] = 1;
} else {
flip(i);
color[i] = lst1 == lst2;
}
cnt0 += color[i] == 0;
s[color[i]].emplace(i);
if (s[0].size() == s[1].size()) {
dnq(s[0], s[1]);
s[0].clear();
s[1].clear();
}
}
}
