#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
int n = N, m = (int)X.size();
vector<int> x = X, y = Y;
vector<int> par(n), sz(n, 1);
iota(par.begin(), par.end(), 0);
auto findd = [&](auto self, int u) -> int
{
return par[u] = (par[u] == u ? u : self(self, par[u]));
};
auto unite = [&](int u, int v) -> bool
{
u = findd(findd, u);
v = findd(findd, v);
if (u == v)
return false;
if (sz[u] > sz[v])
swap(u, v);
sz[v] += sz[u];
par[u] = v;
return true;
};
vector adj(n, vector<int>());
for (int i = 0; i < m; 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());
map<vector<int>, int> mp;
for (int i = 0; i < n - 1; i++)
{
int l = i + 1, r = n - 1, ans = -1;
while (r - l > 1)
{
int md = l + (r - l) / 2;
vector<int> e(n, N);
for (int j = l; j <= md; j++)
e[j] = -1;
if(mp.find(e) == mp.end())
mp[e] = perform_experiment(e);
int cnt = mp[e];
e[i] = -1;
if(mp.find(e) == mp.end())
mp[e] = perform_experiment(e);
int cnt2 = mp[e];
if (cnt2 == cnt)
{
r = md;
}
else
{
l = md + 1;
}
}
vector<int> e(n, N);
e[i] = -1;
e[l] = -1;
if(mp.find(e) == mp.end())
mp[e] = perform_experiment(e);
int cnt = mp[e];
if(n == 2)
{
if(cnt == 1)
unite(i, l);
}
else
{
if(cnt == 2)
unite(i, l);
}
e[i] = -1;
e[l] = N;
e[r] = -1;
if(mp.find(e) == mp.end())
mp[e] = perform_experiment(e);
cnt = mp[e];
if(n == 2)
{
if(cnt == 1)
unite(i, l);
}
else
{
if(cnt == 2)
unite(i, l);
}
// for (int j : adj[i])
// adj[j].erase(find(adj[j].begin(), adj[j].end(), i));
}
set<int> st;
for (int i = 0; i < n; i++)
st.insert(findd(findd, i));
int j = 0;
map<int, int> mp2;
for (auto i : st)
{
mp2[i] = j++;
}
vector<int> res(n);
for (int i = 0; i < n; i++)
res[i] = mp2[findd(findd, i)];
return res;
}
