#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
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;
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
components_cnt++;
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), blues;
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;
blues.push_back(i);
}
}
vector<int> colours(n, -1);
// Find colour of all blue's
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;
}
if (perform_experiment(col) == Count(col)) {
lo = mid + 1;
} else {
hi = mid;
}
}
col[blues[lo]] = c;
colours[blues[lo]] = c;
blues.erase(blues.begin() + lo);
}
}
vector<int> id;
for (int i = 0; i < n; i++) {
if (!blue[i]) {
id.push_back(i);
}
}
mt19937 mt(time(0));
shuffle(all(id), mt);
set<int> relevant_colours;
int neutral;
{
vector<int> col(n, -1);
for (int i = 0; i < n; i++) if (blue[i]) {
col[i] = n;
}
int exp = perform_experiment(col);
for (int c = 0; c < n; c++) {
for (int i = 0; i < n; i++) if (blue[i]) {
col[i] = c;
}
if (perform_experiment(col) != exp) {
relevant_colours.insert(c);
}
}
for (int c = 0; c < n; c++) {
if (relevant_colours.count(c)) continue;
neutral = c;
break;
}
}
map<pair<int, int>, set<int>> ranges;
auto Solve = [&](auto&& self, int lo, int hi, const set<int>& s) -> void {
assert(hi - lo + 1 >= int(s.size()));
if (hi == lo) {
colours[id[lo]] = *s.begin();
return;
}
int mid = lo + (hi - lo) / 2;
if (s.size() == 1) {
self(self, lo, mid, s);
self(self, mid+1, hi, s);
return;
}
set<int> l, r;
auto Col = [&](int c, int tl, int tr) -> vector<int> {
vector<int> col(n, n);
for (int i = 0; i < n; i++) if (blue[i]) {
col[i] = c;
}
for (int i = tl; i <= tr; i++) {
col[id[i]] = -1;
}
return col;
};
int exp_l = -1, exp_r = -1;
for (int c : s) {
if (int(l.size()) == mid - lo + 1) {
r.insert(c);
continue;
}
vector<int> col = Col(c, lo, mid);
if (exp_l == -1) {
exp_l = lo == mid ? Count(Col(neutral, lo, mid)) : perform_experiment(Col(neutral, lo, mid));
}
if (perform_experiment(col) == exp_l) {
r.insert(c);
} else {
l.insert(c);
}
}
for (int c : s) {
if (int(r.size()) == hi - mid) break;
if (r.count(c)) continue;
if (exp_r == -1) {
exp_r = mid+1 == hi ? Count(Col(neutral, mid+1, hi)) : perform_experiment(Col(neutral, mid+1, hi));
}
if (perform_experiment(Col(c, mid+1, hi)) != exp_r) {
r.insert(c);
}
}
self(self, lo, mid, l);
self(self, mid+1, hi, r);
};
Solve(Solve, 0, int(id.size())-1, relevant_colours);
return colours;
}
