#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> E;
const int MAXN = 250;
vector<vector<int>> adj(MAXN);
int expected(int N) {
int cnt = 1;
for (int i = 1; i < N; ++i) {
cnt += (E[i] != E[i - 1]);
}
return cnt;
}
int prepare(int parity, int s, int e, int col, int N) {
cerr << "QUERY WITH [" << s << " , " << e << "]: ";
if (parity == (s & 1)) {
s--;
}
if (parity == (e & 1)) {
e += 1;
}
for (auto& u : E) u = N;
for (int i = max(0, s); i <= min(N - 1, e); ++i) {
if ((i & 1) == parity) E[i] = -1;
else E[i] = col;
}
for (int i = 0; i < N; ++i) {
cerr << E[i] << " ";
}
cerr << "\n";
return expected(N) - perform_experiment(E);
}
void go(int parity, int start, int end, int color, int N, vector<int>& F, int delta) {
int nstart = start;
int nend = end;
if ((start % 2) != parity) nstart++;
if ((nend % 2) != parity) nend--;
if (nstart > nend) return;
if (nstart == nend) {
cerr << "FOUND COLOR = " << color << ", AT " << nstart << "!\n";
F[nstart] = color;
return;
}
int mid = (nstart + nend) / 2;
cerr << "CHECKING NOW COLOR " << color << " , with parity = " << parity << " , at interval = [" << nstart << " , " << mid << "], with end = " << nend << "\n";
// cerr << "INITIAL ARRAY = ";
// for (auto& u : E) {
// cerr << u << " ";
// }
// cerr << "\n";
int diffl = prepare(parity, nstart, mid, color, N);
int diffr = delta - diffl;
cerr << "initial delta = " << delta << " , got left = " << diffl << " , got right = " << diffr << "\n";
if (diffl) go(parity, nstart, mid, color, N, F, diffl);
if (diffr) go(parity, mid, nend, color, N, F, diffr);
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
int M = (int)X.size();
for (int i = 0; i < M; ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
E = vector<int>(N);
vector<int> F(N);
for (int par = 0; par < 2; ++par) {
for (int i = 0; i < N; ++i) {
int nstart = 0, nend = N - 1;
if (nstart % 2 != par) nstart++;
if (nend % 2 != par) nend--;
int delta = prepare(par, nstart, nend, i, N);
if (delta > 0) {
go(par, 0, N - 1, i, N, F, delta);
}
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
E[j] = i;
}
E[N - 2] = -1;
if (perform_experiment(E) == 1) {
F[N - 2] = i;
break;
}
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
E[j] = i;
}
E[N - 1] = -1;
if (perform_experiment(E) == 1) {
F[N - 1] = i;
break;
}
}
return F;
}
