#include "chameleon.h"
//#include <iostream>
#include <set>
#include <vector>
std::set<int> Adj[1001];
std::vector<int> edges[1001];
std::vector<int> groups[4];
int part[1001];
int threeQuery(int x, int y, int z) {
std::vector<int> q;
q.push_back(x);
q.push_back(y);
q.push_back(z);
return Query(q);
}
int queryRange(int l, int r, int group) {
if(l == r)
return 1;
std::vector<int> q;
for(int i = l; i <= r; i++)
q.push_back(groups[group][i]);
return Query(q);
}
int queryRange(int l, int r, int x, int group) {
std::vector<int> q;
for(int i = l; i <= r; i++)
q.push_back(groups[group][i]);
q.push_back(x);
return Query(q);
}
int count(int l, int r, int x, int group) {
return (r-l+2) - queryRange(l, r, x, group);
}
void bs(int x, int l, int r, int group, int c) {
//if(x == 8 || x == 7) {
// std::cout << x << " " << l << " " << r << " " << c << " " << group << std::endl;
//}
if(c == 0)
return;
if(l == r) {
//std::cout << x << " " << groups[group][l] << std::endl;
Adj[x].insert(groups[group][l]);
Adj[groups[group][l]].insert(x);
return;
}
int m = (l+r)/2;
int cl = count(l, m, x, group);
bs(x, l, m, group, cl);
if(Adj[x].size() == 3)
return;
bs(x, m+1, r, group, cl == 0 ? c : count(m+1, r, x, group));
//if(c == 1) {
// if(count(l, m, x, group))
// bs(x, l, m, group, 1);
// else
// bs(x, m+1, r, group, 1);
//}
//else {
// int cl = count(l, m, x, group);
// bs(x, l, m, group, cl);
// if(cl <= 1)
// bs(x, m+1, r, group, 2);
// else {
// bs(x, m+1, r, group, count(m+1, r, x, group));
// }
//}
}
void Solve(int N) {
for(int i = 0; i < 4; i++) {
groups[i].push_back(i+1);
part[i+1] = i;
}
for(int i = 5; i <= 2*N; i++) {
for(int j = 0; j < 4; j++) {
groups[j].push_back(i);
if(Query(groups[j]) == groups[j].size()) {
part[i] = j;
break;
}
else
groups[j].pop_back();
}
}
//std::cout << "groups" << std::endl;
//for(int i = 0; i < 4; i++) {
// for(int j : groups[i])
// std::cout << j << " ";
// std::cout << std::endl;
//}
for(int i = 1; i <= 2*N; i++) {
for(int j = part[i]+1; j < 4; j++) {
if(Adj[i].size() == 3)
break;
int c = count(0, groups[j].size()-1, i, j);
//std::cout << i << " " << j << " " << c << std::endl;
bs(i, 0, groups[j].size()-1, j, c);
}
}
for(int i = 1; i <= 2*N; i++) {
if(Adj[i].size() == 3) {
for(std::set<int>::iterator it = Adj[i].begin(); it != Adj[i].end(); it++) {
edges[i].push_back(*it);
}
}
}
for(int i = 1; i <= 2*N; i++) {
if(edges[i].size() == 3) {
int x0 = threeQuery(i, edges[i][1], edges[i][2]);
int x1 = threeQuery(i, edges[i][0], edges[i][2]);
int x;
if(x0 == 1)
x = edges[i][0];
else if(x1 == 1)
x = edges[i][1];
else
x = edges[i][2];
Adj[x].erase(i);
Adj[i].erase(x);
}
}
for(int i = 1; i <= 2*N; i++) {
int j = *Adj[i].begin();
if(i < j)
Answer(i, j);
}
}
