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