#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
//////////////////////////////////////////////////////////////////
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
auto n = N, m = (int)X.size();
auto x = X, y = Y;
vector<int> col(n, 0);
for (int i = 0; i < n; i++)col[i] = i;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++)
graph[x[i]].push_back(y[i]),
graph[y[i]].push_back(x[i]);
function<int(int)> fnd = [&](int x)
{
if (col[x]==x)return x;
return col[x] = fnd(col[x]);
};
auto povezan = [&](vector<int> tuff, int idx)
{
vector<int> salji(n, n);
for (int i : tuff)
salji[i] = -1;
vector<bool> vis(n,0);
function<void(int)> dfs = [&](int cur)
{
if (vis[cur] || salji[cur] != n)
return;
vis[cur] = 1;
for (int a : graph[cur])
dfs(a);
};
salji[idx] = -1;
set<int> dif;
for (int i : tuff)
dif.insert(fnd(col[i]));
int comps = dif.size();
for (int i = 0; i < n; i++)
if (!vis[i] && salji[i] == n)
{
comps++;
dfs(i);
}
return perform_experiment(salji) <= comps;
};
vector<int> pref;
pref.push_back(0);
for (int i = 1; i < n; i++)
{
if (povezan(pref,i))
{
set<int> used;
vector<int> space;
for (int a : graph[i])
if (a < i && used.count(fnd(col[a]))==0)
space.push_back(a),used.insert(col[a]);
int k = space.size();
auto fnd_next = [&](int cur)
{
int bg = lower_bound(space.begin(),space.end(),cur)-space.begin();
int l = bg;
int r = k;
auto check = [&](int bnd)
{
if (bnd==k)return true;
vector<int> src;
for (int j = bg; j <= bnd; j++)
src.push_back(space[j]);
return povezan(src,i);
};
while(r-l)
{
int mid = l+r>>1;
if (check(mid))
r = mid;
else
l = mid+1;
}
return l;
};
int cur = fnd_next(0);
while(cur < k)
{
col[fnd(space[cur])] = i;
cur = fnd_next(space[cur]+1);
}
}
pref.push_back(i);
}
for (int i = 0; i < n; i++)
col[i] = fnd(i);
return col;
}
///////////////////////////////////////////////////////////////////
