#include <bits/stdc++.h>
#include "chameleon.h"
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
int n,l[1000],xr[1002],qr=0;
int cm[1000],cl[1002];
bool c[1000],c1[1000],cnt[1002];
vector<int> g[1002],cur1,cur;
queue<int> qu;
void bfs(int x) {
while(sz(qu)) qu.pop();
cl[x]=0;
qu.push(x);
while(sz(qu)) {
int u=qu.front();
qu.pop();
for(auto v: g[u])
if (cl[v]==-1) {
cl[v]=!cl[u];
qu.push(v);
}
}
}
void add(int u) {
if (cur1.empty()) return;
vector<int> tmp;
tmp=cur1;
tmp.pb(u);
if (Query(tmp)>=sz(tmp)) return;
int j=0;
tmp.clear();
while(j<sz(cur1)) {
tmp.clear();
For(i,j,sz(cur1)-1) tmp.pb(cur1[i]);
tmp.pb(u);
if (j>=sz(cur1) || Query(tmp)>=sz(tmp)) return;
int l=j,r=sz(cur1)-1;
while(l<r) {
int mid=l+(r-l)/2;
tmp.clear();
For(i,j,mid) tmp.pb(cur1[i]);
tmp.pb(u);
if (Query(tmp)<sz(tmp)) r=mid;
else l=mid+1;
}
g[u].pb(cur1[l]);
g[cur1[l]].pb(u);
j=l+1;
}
}
void Solve(int N) {
n=N;
For(i,1,n*2) g[i].clear();
For(i,1,n*2) {
for(auto el: cur) cl[el]=-1;
for(auto el: cur)
if (cl[el]==-1) bfs(el);
cur1.clear();
for(auto el: cur)
if (cl[el]) cur1.pb(el);
add(i);
cur1.clear();
for(auto el: cur)
if (!cl[el]) cur1.pb(el);
add(i);
cur.pb(i);
}
// For(i,1,n*2) {
// cout << i << endl;
// for(auto el: g[i]) cout << el << " ";
// cout << endl;
// }
vector<int> tmp;
For(i,1,n*2)
if (sz(g[i])==3) {
tmp.clear();
tmp.pb(i),tmp.pb(g[i][0]),tmp.pb(g[i][1]);
if (Query(tmp)==1) xr[i]=g[i][2];
else {
tmp.pop_back();
tmp.pb(g[i][2]);
if (Query(tmp)==1) xr[i]=g[i][1];
else xr[i]=g[i][0];
}
}
For(i,1,n*2) {
if (cnt[i]) continue;
if (sz(g[i])==1) {
cnt[i]=cnt[g[i][0]]=1;
Answer(i,g[i][0]);
} else {
for(auto el: g[i]) {
if (el!=xr[i] && ((sz(g[el])==1 && g[el][0]==i) || (sz(g[el])==3 && xr[el]!=i))) {
Answer(el,i);
cnt[el]=cnt[i]=1;
break;
}
}
}
}
}
