#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;
// 1. Linearizace grafu (převedení na cestu)
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; // Pořadí vrcholů na cestě
{
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 = false;
for (int neighbor : adj[curr]) {
if (!vis[neighbor]) {
curr = neighbor;
found = true;
break;
}
}
if (!found) break;
}
}
vector<int> colors(n, -1);
vector<int> a(n);
// 2. Hlavní smyčka: Iterujeme přes barvy, které hledáme
for (int c = 0; c < n; c++) {
// Pro každou barvu projdeme tři možná posunutí (modulo 3), aby se páry nepřekrývaly
for (int k = 0; k < 3; k++) {
// Helper funkce: Spočítá shody v podmnožině kandidátů
// candidates: seznam indexů 'j', které testujeme
// l, r: rozsah v poli candidates (ne v grafu!)
auto count_matches = [&](const vector<int>& candidates, int l, int r) {
if (l > r) return 0;
// Reset na Sphinx barvu (N)
fill(a.begin(), a.end(), n);
int active_cnt = 0;
for (int i = l; i <= r; i++) {
int j = candidates[i];
// Testujeme pár: ord[j] (original) -- ord[j+1] (barva c)
a[ord[j]] = -1;
a[ord[j+1]] = c;
active_cnt++;
}
if (active_cnt == 0) return 0;
// Každé úspěšné spojení sníží počet komponent o 1 oproti očekávání
// Očekávaný počet (pokud se nic nespojí) = N
// Počet komponent = N - matches
int matches = n - perform_experiment(a);
return matches;
};
// Smyčka pro nalezení všech výskytů barvy c v aktuálním posunu k
while (true) {
// Vytvoříme seznam validních kandidátů pro tento krok
// Kandidát je index 'j', kde j%3==k a barvu ord[j] ještě neznáme
vector<int> candidates;
for (int j = k; j < n - 1; j += 3) {
if (colors[ord[j]] == -1) {
candidates.push_back(j);
}
}
if (candidates.empty()) break;
// Rychlý check: je vůbec v celém seznamu kandidátů nějaká shoda?
int total = count_matches(candidates, 0, candidates.size() - 1);
if (total == 0) break; // Žádná další shoda pro barvu 'c' a posun 'k'
// Binary search: hledáme PRVNÍ index v candidates, který způsobí spojení
int l = 0, r = candidates.size() - 1;
int found_idx_in_candidates = -1;
while (l <= r) {
if (l == r) {
found_idx_in_candidates = l;
break;
}
int mid = l + (r - l) / 2;
// Pokud je shoda v levé polovině, jdeme doleva
if (count_matches(candidates, l, mid) > 0) {
r = mid;
} else {
l = mid + 1;
}
}
if (found_idx_in_candidates != -1) {
int real_j = candidates[found_idx_in_candidates];
colors[ord[real_j]] = c; // Našli jsme barvu!
// Cyklus pokračuje (while true), znovu sestaví kandidáty (bez tohoto j) a hledá další
} else {
break;
}
}
}
}
// 3. Dořešení posledního vrcholu (ord[n-1])
// Protože hlavní smyčka testuje páry (j, j+1), nikdy nezjistí barvu pro j = n-1.
// Jednoduše projdeme barvy a zkusíme ho spojit s předposledním vrcholem.
// Toto stojí max N dotazů, což se do limitu 2750 vejde (N <= 250).
if (colors[ord[n - 1]] == -1) {
for (int c = 0; c < n; c++) {
fill(a.begin(), a.end(), n);
// Nastavíme předposlední na 'c', poslední na -1
a[ord[n - 2]] = c;
a[ord[n - 1]] = -1;
// Pokud se spojí, počet komponent bude < N
if (perform_experiment(a) < n) {
colors[ord[n - 1]] = c;
break;
}
}
}
// Fallback: Pokud něco zůstalo -1 (nemělo by), nastavíme na 0
for(int i=0; i<n; i++) if(colors[i] == -1) colors[i] = 0;
return colors;
}
