#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
using uLL = unsigned long long int;
using uint = unsigned int;
using ld = long double;
const int MAXN = 1007;
vector <int> group[MAXN];
vector <int> structure[4];
int ans[MAXN], beloved[MAXN], beloving[MAXN];
vector <vector <int> > indices = {{0, 1}, {0, 2}};
vector <int> not_present = {2, 1};
vector <int> sub_vector(int l, int r, vector <int> &w){
if(l > r){
vector <int> res;
return res;
}
vector <int> res(r-l);
for(int i = l; i < r; i++){
res[i-l] = w[i];
}
return res;
}
int binarysearch(int l, int r, int id, int g){
//cout << "G " << id << " " << g << " " << l << " " << r << '\n';
while(l+1 < r){
int mid = (l+r)>>1;
//cout << l << " " << mid << " " << r << '\n';
vector <int> temp = sub_vector(l+1, mid+1, structure[g]);
temp.push_back(id);
if(Query(temp) == int(temp.size())){
l = mid;
}
else{
r = mid;
}
}
return r;
}
void update(int id){
//cout << "ID " << id << '\n';
bool czy = false;
int licz = 0;
for(int g = 0; g < 4; g++){
vector <int> temp = structure[g];
temp.push_back(id);
if(licz == 3 || structure[g].empty() || Query(temp) == int(temp.size())){
if(!czy){
structure[g].push_back(id);
//cout << "ADD " << g << " " << id << '\n';
czy = true;
}
}
else{
int l = -1;
int r = int(structure[g].size())-1;
do{
int x = binarysearch(l, r, id, g);
group[structure[g][x]].push_back(id);
group[id].push_back(structure[g][x]);
//cout << "UP " << structure[g][x] << '\n';
l = x;
temp = sub_vector(l+1, r+1, structure[g]);
temp.push_back(id);
licz++;
//cout << (licz < 3) << " " << (l < r) << '\n';
}while(licz < 3 && l < r && Query(temp) < int(temp.size()));
}
}
}
void make_edge(int id){
if(group[id].size() == 1){
return;
}
/*cout << "GROUP " << id << '\n';
for(auto x: group[id]){
cout << x << " ";
}
cout << '\n';*/
for(int i = 0; i < 2; i++){
vector <int> temp = {id, group[id][indices[i][0]], group[id][indices[i][1]]};
if(Query(temp) == 1){
beloved[id] = group[id][not_present[i]];
beloving[group[id][not_present[i]]] = id;
return;
}
}
beloved[id] = group[id][0];
beloving[group[id][0]] = id;
return;
}
void process_ans(int id){
for(auto x: group[id]){
if(x != beloved[id] && x != beloving[id]){
ans[id] = x;
}
}
}
void Solve(int N){
vector <int> tab(2*N);
iota(tab.begin(), tab.end(), 1);
srand(N);
random_shuffle(tab.begin(), tab.end());
for(auto x: tab){
update(x);
}
for(int i = 1; i <= 2*N; i++){
make_edge(i);
}
for(int i = 1; i <= 2*N; i++){
process_ans(i);
}
/*for(int i = 1; i <= 2*N; i++){
cout << ans[i] << '\n';
}*/
for(int i = 1; i <= 2*N; i++){
if(i < ans[i]){
Answer(i, ans[i]);
}
}
}
