#include <bits/stdc++.h> #include "sphinx.h" using namespace std; std::vector<int> find_colours(int N, std::vector<int> X, std::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> ord; vector<bool> vis(n, false); int start_node = 0; for (int i = 0; i < n; i++) { if (adj[i].size() == 1) { start_node = i; break; } } int curr = start_node; while (true) { vis[curr] = true; ord.push_back(curr); bool found_next = false; for (int neighbor : adj[curr]) { if (!vis[neighbor]) { curr = neighbor; found_next = true; break; } } if (!found_next) break; } vector<int> colors(n, -1); vector<int> a(n); int identified = 0; for (int c = 0; c < n; c++) { if (identified == n) break; for (int k = 0; k < 3; k++) { set<int> found_indices; auto get_matches = [&](int l, int r) { fill(a.begin(), a.end(), n); int active_pairs = 0; for (int j = k; j < n - 1; j += 3) { if (j >= l && j <= r) { if (found_indices.count(j)) continue; if (colors[ord[j]] != -1) continue; a[ord[j]] = -1; a[ord[j+1]] = c; active_pairs++; } } if (active_pairs == 0) return 0; int components = perform_experiment(a); return n - components; }; int total_matches = get_matches(0, n - 2); while (total_matches > 0) { int l = 0, r = n - 2; int found_pos = -1; while (l <= r) { if (l == r) { if (l % 3 == k) found_pos = l; break; } int mid = l + (r - l) / 2; if (get_matches(l, mid) > 0) { r = mid; } else { l = mid + 1; } } if (found_pos != -1) { colors[ord[found_pos]] = c; identified++; found_indices.insert(found_pos); total_matches--; } else { break; } } } } for (int i = 0; i < n; i++) { if (colors[i] == -1) colors[i] = 0; } return colors; }