#include "chameleon.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
const int MAXN = 1000 + 10;
namespace
{
int n;
int perm[MAXN];
int before[MAXN];
bool found[2 * MAXN];
std::vector <int> candidates[MAXN];
std::vector <int> x, y;
}
int runBinary(int fromPos, std::vector <int> &from, int value)
{
int l = fromPos - 1, r = from.size(), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::vector <int> curr;
curr.push_back(value);
for (int j = fromPos ; j <= mid ; ++j)
{
curr.push_back(from[j]);
}
if (Query(curr) == curr.size()) l = mid;
else r = mid;
}
return r;
}
int timer;
int vis[MAXN];
void rebuild(int node, int side)
{
if (side == 0)
{
x.push_back(node);
} else
{
y.push_back(node);
}
vis[node] = timer;
for (const int &u : candidates[node])
{
if (vis[u] != timer)
{
rebuild(u, side ^ 1);
}
}
}
void Solve(int n)
{
::n = n;
for (int i = 1 ; i <= 2 * n ; ++i)
{
timer++;
bool shouldTryX = true;
bool shouldTryY = true;
x.push_back(i);
y.push_back(i);
if (Query(x) == x.size())
{
shouldTryX = false;
}
if (Query(y) == y.size())
{
shouldTryY = false;
}
x.pop_back();
y.pop_back();
int cntFound = 0;
if (shouldTryX)
{
int lastAdded = -1;
while (cntFound < 3 && lastAdded + 1 < x.size())
{
int curr = runBinary(lastAdded + 1, x, i);
if (curr != x.size())
{
candidates[i].push_back(x[curr]);
candidates[x[curr]].push_back(i);
cntFound++;
}
lastAdded = curr;
}
}
if (shouldTryY)
{
int lastAdded = -1;
while (cntFound < 3 && lastAdded + 1 < y.size())
{
int curr = runBinary(lastAdded + 1, y, i);
if (curr != y.size())
{
candidates[i].push_back(y[curr]);
candidates[y[curr]].push_back(i);
cntFound++;
}
lastAdded = curr;
}
}
x.clear();
y.clear();
for (int u = 1 ; u <= i ; ++u)
{
if (vis[u] != timer)
{
rebuild(u, 0);
}
}
}
for (int i = 1 ; i <= 2 * n ; ++i)
{
if (candidates[i].size() == 3)
{
if (Query({candidates[i][0], candidates[i][2], i}) == 1)
{
std::swap(candidates[i].back(), candidates[i][1]);
} else if (Query({candidates[i][1], candidates[i][2], i}) == 1)
{
std::swap(candidates[i].back(), candidates[i][0]);
}
candidates[i].pop_back();
}
}
std::iota(perm + 1, perm + 1 + 2 * n, 1);
for (int idx = 1 ; idx <= 2 * n ; ++idx)
{
int i = perm[idx];
if (found[i])
{
continue;
}
if (candidates[i].size() == 1)
{
Answer(i, candidates[i][0]);
found[candidates[i][0]] = true;
continue;
}
assert(candidates[i].size() == 2);
bool shouldBreak = false;
for (const int &j : candidates[i])
{
for (const int &x : candidates[j])
{
if (x == i)
{
Answer(i, j);
found[j] = true;
shouldBreak = true;
break;
}
}
if (shouldBreak)
{
break;
}
}
}
}
