#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
vector <int> ve[1001],tmp,V[2];
int L[1001],c[1001],vis[1001],done[1001];
}
int get(int i, int l, int r, vector <int> v){
tmp.clear();
tmp.push_back(i);
for (int i=l;i<=r;i++)
tmp.push_back(v[i]);
if (Query(tmp)==r-l+2)
return -1;
int lo=l,hi=r-1,kq=r;
while (lo<=hi){
int mid=(lo+hi)>>1;
tmp.clear();
tmp.push_back(i);
for (int i=l;i<=mid;i++)
tmp.push_back(v[i]);
if (Query(tmp)<mid-l+2){
kq=mid;
hi=mid-1;
}
else
lo=mid+1;
}
return kq;
}
vector <int> getall(int i, vector <int> v){
int cur=0;
vector <int> res;
while (cur<v.size()&&res.size()<3){
cur=get(i,cur,v.size()-1,v);
if (cur==-1)
break;
res.push_back(v[cur]);
cur++;
}
return res;
}
vector <int> operator +(vector <int> a, vector <int> b){
for (int i:b)
a.push_back(i);
return a;
}
void dfs(int u, int C){
if (vis[u])
return;
vis[u]=1;
c[u]=C;
V[C].push_back(u);
for (int v:ve[u])
dfs(v,C^1);
}
void Solve(int N){
for (int i=1;i<=N*2;i++){
memset(vis,0,sizeof(vis));
memset(c,0,sizeof(c));
V[0].clear();
V[1].clear();
for (int j=1;j<i;j++)
if (!vis[j])
dfs(j,0);
ve[i]=getall(i,V[0])+getall(i,V[1]);
for (int j:ve[i])
ve[j].push_back(i);
}
for (int i=1;i<=N*2;i++){
if (ve[i].size()==1){
if (ve[i][0]>i){
Answer(i,ve[i][0]);
done[i]=done[ve[i][0]]=1;
}
continue;
}
if (Query({i,ve[i][0],ve[i][1]})<2){
L[ve[i][2]]=i;
continue;
}
if (Query({i,ve[i][0],ve[i][2]})<2){
L[ve[i][1]]=i;
continue;
}
L[ve[i][0]]=i;
}
for (int i=1;i<=N*2;i++){
if (ve[i].size()>1&&L[i]&&!done[i]){
vector <int> tmp={i,L[i]};
for (int j:ve[i])
if (j!=L[i])
tmp.push_back(j);
int x=tmp.back();
tmp.pop_back();
int j=Query(tmp)<2?tmp.back():x;
done[i]=done[j]=1;
Answer(i,j);
continue;
}
}
}
