#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; }