#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif
vector<int> find_colours(int n, vector<int> u, vector<int> v) {
const int m = int(u.size());
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
auto Count = [&](const vector<int>& S) {
int components_cnt = 0;
std::vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
components_cnt++;
std::queue<int> q;
vis[i] = true;
q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int nxt : adj[cur]) {
if (!vis[nxt] && S[nxt] == S[cur]) {
vis[nxt] = true;
q.push(nxt);
}
}
}
}
return components_cnt;
};
vector<int> blue(n, 0), b, r;
for (int i = 0; i < n; i++) {
bool go_blue = true;
for (auto node : adj[i]) {
if (blue[node]) {
go_blue = false;
}
}
if (go_blue) {
blue[i] = 1;
b.push_back(i);
} else {
r.push_back(i);
}
}
vector<int> colours(n, -1);
// Find colour of all blue's
auto SolveReds = [&](vector<int> &blues) {
for (int c = 0; c < n; c++) {
vector<int> col(n, c);
for (int i : blues) { col[i] = -1; }
int initial_experiment = perform_experiment(col);
while (!blues.empty() && Count(col) != initial_experiment) {
int lo = 0, hi = int(blues.size()) - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
for (int i : blues) { col[i] = n; };
for (int i = lo; i <= mid; i++) {
col[blues[i]] = -1;
}
int perf = perform_experiment(col), cnt = Count(col);
if (perf == cnt) {
lo = mid + 1;
} else {
hi = mid;
}
}
col[blues[lo]] = c;
colours[blues[lo]] = c;
blues.erase(blues.begin() + lo);
}
}
};
SolveReds(r);
SolveReds(b);
return colours;
}
