#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 250;
int n, m;
int vert;
int parent[MAX_N];
int depth[MAX_N];
bool vis[MAX_N];
int finalColor[MAX_N];
vector<int> adj[MAX_N];
vector<int> adjComp[MAX_N];
vector<int> comp[MAX_N];
mt19937 rnd(1010);
int findParent(int v) {
if (parent[v] != v)
parent[v] = findParent(parent[v]);
return parent[v];
}
void unionn(int u, int v) {
// printf("UNESC %d %d\n", u, v);
u = findParent(u);
v = findParent(v);
if (u == v)
return;
parent[u] = v;
}
int ask(vector<int> v) {
vector<int> e(n, n);
for (int i: v)
e[i] = -1;
e[vert] = -1;
int a = perform_experiment(e);
for (int i: v)
e[i] = 0;
e[vert] = 0;
int b = perform_experiment(e);
return v.size() - a + b;
}
void divide(vector<int> cand, int c) {
shuffle(cand.begin(), cand.end(), rnd);
int n = cand.size();
if (n == 0)
return;
if (c == -1)
c = ask(cand);
if (c == 0)
return;
if (n == 1) {
unionn(vert, cand[0]);
return;
}
vector<int> a, b;
for (int i = 0; i < n / 2; i++)
a.push_back(cand[i]);
for (int i = n / 2; i < n; i++)
b.push_back(cand[i]);
int aa = ask(a);
int bb = c - aa;
if (aa > 0)
divide(a, aa);
if (bb > 0)
divide(b, bb);
}
void findSpan(int u) {
vis[u] = true;
for (int v: adjComp[u]) {
if (vis[v])
continue;
depth[v] = depth[u] + 1;
findSpan(v);
}
}
int color;
int totalComp;
vector<int> fixedC;
int ask2(vector<int> v) {
vector<int> e(n, 0);
int clr = 0;
for (int v = 0; v < n; v++) {
if (findParent(v) != v)
continue;
while (clr == color)
clr++;
for (int u: comp[v])
e[u] = clr;
clr++;
}
for (int i: fixedC) {
for (int v: comp[i])
e[v] = color;
}
for (int i: v) {
// printf("%d\n", i);
for (int v: comp[i])
e[v] = -1;
}
int a = perform_experiment(e);
return totalComp - a;
}
void divide2(vector<int> cand, int ans) {
shuffle(cand.begin(), cand.end(), rnd);
int n = cand.size();
if (n == 0)
return;
if (ans == -1)
ans = ask2(cand);
if (ans == 0)
return;
if (n == 1) {
// printf("AM DECIS %d %d\n", cand[0], color);
finalColor[cand[0]] = color;
return;
}
vector<int> a, b;
for (int i = 0; i < n / 2; i++)
a.push_back(cand[i]);
for (int i = n / 2; i < n; i++)
b.push_back(cand[i]);
int aa = ask2(a);
int bb = ans - aa;
if (aa > 0)
divide2(a, aa);
if (bb > 0)
divide2(b, bb);
}
void findColors(int c, int p) {
vector<int> cand;
fixedC.clear();
color = c;
for (int v = 0; v < n; v++) {
if (findParent(v) != v)
continue;
if (depth[v] % 2 == p)
cand.push_back(v);
else
fixedC.push_back(v);
}
divide2(cand, -1);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
n = N;
m = X.size();
for (int i = 0; i < m; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int v = 0; v < n; v++)
parent[v] = v;
for (int v = 1; v < n; v++) {
vector<int> cand;
set<int> s;
for (int u: adj[v]) {
if (u < v) {
if (s.find(findParent(u)) == s.end()) {
s.insert(findParent(u));
cand.push_back(u);
}
}
}
// printf("CAND ");
// for (int u: cand)
// printf("%d ", u);
// printf("\n");
vert = v;
divide(cand, -1);
}
for (int v = 0; v < n; v++) {
comp[findParent(v)].push_back(v);
for (int u: adj[v])
adjComp[findParent(v)].push_back(findParent(u));
}
for (int v = 0; v < n; v++) {
if (findParent(v) != v)
continue;
totalComp++;
sort(adjComp[v].begin(), adjComp[v].end());
adjComp[v].resize(unique(adjComp[v].begin(), adjComp[v].end()) - adjComp[v].begin());
}
findSpan(0);
for (int c = 0; c < n; c++) {
findColors(c, 0);
findColors(c, 1);
}
vector<int> ans(n);
for (int v = 0; v < n; v++)
ans[v] = finalColor[findParent(v)];
return ans;
}
