#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;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
for (int i = 0; i < X.size(); i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
n = N;
DSU dsu;
dsu.init(n);
int comps[N];
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] = perform_experiment(q) - cntNs(q);
// cout << comps[i] << ' ';
if (!i || comps[i] == comps[i - 1] + 1) continue;
int cnt = comps[i - 1] - comps[i] + 1;
for (int k = 1, l = 0; k <= cnt; k++)
{
int r = i - 1;
while (l < r)
{
int mid = (l + r) >> 1;
vector<int> c(n, n);
for (int l = 0; l <= mid; l++) c[l] = -1;
c[i] = -1;
int val = perform_experiment(c) - cntNs(c);
if (comps[mid] + 1 - k == val) r = mid;
else l = mid + 1;
}
dsu.unite(i, l);
}
}
// cout << '\n';
vector<int> res(n, 0);
for (int i = 0, idx = 0; i < n; i++)
{
if (dsu.get(i) != i) continue;
res[i] = idx++;
}
for (int i = 0; i < n; i++) res[i] = res[dsu.get(i)];
return res;
}
