#include "sphinx.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
std::vector<int> find_colours(int n, std::vector<int> X, std::vector<int> Y){
int m = (int)X.size();
vector<vector<int>> graph(n);
for(int i = 0; i < m; i++){
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
vector<int> que(n), ans(n, -1), imp;
for(int i = 2; i < n; i += 2) imp.push_back(i);
for(int col = 0; col < n; col++){
fill(que.begin(), que.end(), -1);
for(int i = 1; i < n; i += 2) que[i] = col;
que[0] = n;
int res = perform_experiment(que);
if(res == n) continue;
res = n - res;
if(res & 1){
ans[n - 1] = col;
res--;
}
res /= 2;
int lst = 0;
int sz = (int)imp.size();
for(int times = 0; times < res; times++){
int l = lst, r = sz - 1;
while(l < r){
int mid = (l + r) >> 1;
for(int i = 0; i <= mid; i++){
que[imp[i]] = n;
}
for(int i = mid + 1; i < sz; i++){
que[imp[i]] = -1;
}
int ress = perform_experiment(que);
ress = (n - ress) / 2;
if(ress == res - times) l = mid + 1;
else r = mid;
}
ans[imp[l]] = col;
lst = l + 1;
}
}
vector<int>().swap(imp);
for(int i = 1; i < n; i += 2) imp.push_back(i);
for(int col = 0; col < n; col++){
fill(que.begin(), que.end(), -1);
for(int i = 0; i < n; i += 2) que[i] = col;
int res = perform_experiment(que);
if(res == n) continue;
res = n - res;
if(res & 1){
ans[n - 1] = col;
res--;
}
res /= 2;
int lst = 0;
int sz = (int)imp.size();
for(int times = 0; times < res; times++){
int l = lst, r = sz - 1;
while(l < r){
int mid = (l + r) >> 1;
for(int i = 0; i <= mid; i++){
que[imp[i]] = n;
}
for(int i = mid + 1; i < sz; i++){
que[imp[i]] = -1;
}
int ress = perform_experiment(que);
ress = (n - ress) / 2;
if(ress == res - times) l = mid + 1;
else r = mid;
//cout << col << " " << mid << " " << ress << " " << res - times << endl;
}
ans[imp[l]] = col;
lst = l + 1;
}
}
for(int col = 0; col < n; col++){
fill(que.begin(), que.end(), col);
que[0] = -1;
if(perform_experiment(que) == 1){
ans[0] = col;
break;
}
}
return ans;
}
