#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 250;
struct DSU
{
vector<int> e;
void init(int n)
{
e.assign(n, -1);
}
int get(int x)
{
if (e[x] < 0) return x;
return e[x] = get(e[x]);
}
void unite(int x, int y)
{
x = get(x), y = get(y);
if (x == y) return;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
}
};
int n;
vector<int> adj[MXN], g[MXN];
int bic[MXN], u[MXN];
void bicol(int a)
{
u[a] = 1;
for (int &v : g[a])
{
if (u[v]) continue;
bic[v] = bic[a] ^ 1;
bicol(v);
}
}
void dfs(int a, vector<int> &used, vector<int> &col)
{
used[a] = 1;
for (int &v : adj[a])
{
if (used[v] || col[v] == -1) continue;
dfs(v, used, col);
}
}
int cntNs(vector<int> &col)
{
int res = 0;
vector<int> used(n, 0);
for (int i = 0; i < n; i++)
{
if (!used[i] && col[i] != -1) res++, dfs(i, used, col);
}
return res;
}
int getcomps(vector<int> &col)
{
return perform_experiment(col) - cntNs(col);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
n = N;
for (int i = 0; i < X.size(); i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
DSU dsu;
dsu.init(n);
vector<vector<int>> cc;
for (int i = 0; i < n; i++)
{
vector<int> q(n, 0);
for (int j = 0; j <= i; j++) q[j] = -1;
for (int j = i + 1; j < n; j++) q[j] = n;
int cur = getcomps(q);
cc.push_back({i});
if (!i || cur == cc.size()) continue;
vector<int> del(cc.size(), 0);
int cnt = (int)cc.size() - cur;
for (int k = 1, l = 0; k <= cnt; k++)
{
int r = (int)cc.size() - 2;
while (l < r)
{
int mid = (l + r) >> 1;
vector<int> q(n, n);
for (int i = l; i <= mid; i++)
{
for (int &j : cc[i]) q[j] = -1;
}
q[i] = -1;
if (getcomps(q) <= mid - l + 1) r = mid;
else l = mid + 1;
}
for (int &j : cc[l]) cc.back().push_back(j);
del[l] = 1;
l++;
}
for (int i = (int)cc.size() - 1; i >= 0; i--) if (del[i]) cc.erase(cc.begin() + i);
}
vector<int> comp(n, 0);
for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) comp[j] = i;
for (int i = 0; i < X.size(); i++)
{
if (comp[X[i]] != comp[Y[i]]) g[comp[X[i]]].push_back(comp[Y[i]]), g[comp[Y[i]]].push_back(comp[X[i]]);
}
for (int i = 0; i < cc.size(); i++)
{
if (!u[i]) bicol(i);
}
vector<int> real(cc.size());
for (int val = 0; val < n; val++)
{
for (int p = 0; p < 2; p++)
{
vector<int> q(n, val);
int cnt = 0;
for (int i = 0; i < cc.size(); i++)
{
if (bic[i] == p) q[cc[i][0]] = -1, cnt++;
}
int cur = perform_experiment(q);
int valcomps = cntNs(q);
// cur = valcomps + cnt
for (int l = 0; cur < valcomps + cnt;)
{
int r = (int)cc.size() - 1;
while (l < r)
{
int mid = (l + r) >> 1;
vector<int> q(n, val);
int cnt = 0;
for (int i = l; i <= mid; i++)
{
if (bic[i] == p) q[cc[i][0]] = -1, cnt++;
}
if (getcomps(q) == cnt) l = mid + 1;
else r = mid;
}
real[l] = val;
cnt--;
q[cc[l][0]] = val;
valcomps = cntNs(q);
l++;
}
}
}
vector<int> res(n, 0);
for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) res[j] = real[i];
return res;
}
