#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
int n = N;
vector<vector<int>> adj(n);
for (size_t i = 0; i < X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> colors(n, -1);
vector<int> ord;
vector<bool> vis(n, false);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
vis[i] = true;
ord.push_back(i);
queue<int> q;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
ord.push_back(v);
q.push(v);
}
}
}
}
}
vector<int> query_array(n);
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> find_set = [&](int v) {
return v == p[v] ? v : p[v] = find_set(p[v]);
};
auto unite_sets = [&](int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) p[b] = a;
};
for (int u : ord) {
map<int, vector<int>> neighbor_groups;
for (int v : adj[u]) {
if (colors[v] != -1) {
neighbor_groups[colors[v]].push_back(v);
}
}
vector<int> candidate_colors;
for (auto const& [color, nodes] : neighbor_groups) {
candidate_colors.push_back(color);
}
int found_color = -1;
int l = 0, r = candidate_colors.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
vector<int> test_colors;
for(int i = l; i <= mid; ++i) test_colors.push_back(candidate_colors[i]);
vector<int> S;
for (int c : test_colors) {
for (int v : neighbor_groups[c]) S.push_back(v);
}
if (S.empty()) {
l = mid + 1;
continue;
}
for(int v : S) p[v] = v;
p[u] = u;
for (int v : S) {
for (int w : adj[v]) {
if (colors[w] == colors[v]) {
bool is_in_S = false;
for(int check : S) if(check == w) is_in_S = true;
if(is_in_S) unite_sets(v, w);
}
}
}
int expected_internal_components = 0;
vector<int> unique_roots;
for(int v : S) {
int root = find_set(v);
bool new_root = true;
for(int existing : unique_roots) if(existing == root) new_root = false;
if(new_root) {
unique_roots.push_back(root);
expected_internal_components++;
}
}
fill(query_array.begin(), query_array.end(), n);
for(int v : S) query_array[v] = -1;
query_array[u] = -1;
for(int i=0; i<n; ++i) {
bool in_set = (i == u);
for(int v : S) if(v == i) in_set = true;
if(!in_set) query_array[i] = i;
}
int actual_components = perform_experiment(query_array);
int outside_nodes = n - (S.size() + 1);
int expected_total = outside_nodes + expected_internal_components + 1;
if (actual_components < expected_total) {
found_color = -2;
if (l == mid) {
found_color = candidate_colors[l];
break;
}
r = mid;
} else {
l = mid + 1;
}
}
if (found_color >= 0) {
colors[u] = found_color;
} else {
int max_c = -1;
for(int c : colors) max_c = max(max_c, c);
colors[u] = max_c + 1;
}
}
for (int i = 0; i < n; i++) {
if (colors[i] == -1) colors[i] = 0;
}
return colors;
}
