#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];
void dfs(int a, vector<int> &used, vector<int> &col)
{
used[a] = 1;
for (int &v : adj[a])
{
if (used[v] || col[v] != n) 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] == n) 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]);
for (int i = 0; i < n; i++) sort(adj[i].begin(), adj[i].end());
DSU dsu;
dsu.init(n);
int comps[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;
comps[i] = getcomps(q);
if (!i || comps[i] == comps[i - 1] + 1)
{
cc.push_back({i});
continue;
}
cc.push_back({i});
vector<int> del(cc.size(), 0);
int cnt = comps[i - 1] + 1 - comps[i];
for (int k = 1, l = 0; k <= cnt; k++)
{
int r = (int)cc.size() - 1;
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> res(n, 0);
for (int i = 0; i < cc.size(); i++) for (int &j : cc[i]) res[j] = i;
return res;
}
