#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
#define ll long long
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
// Pomocná funkce pro nastavení barev pro experiment
// target_color: barva, kterou testujeme
// k: modulo posun (0, 1, 2)
// l, r: rozsah pro binary search (kde jsou aktivní testy)
// ord: seřazené vrcholy cesty
// found: indexy, které už jsme pro tuto barvu našli (aby se nepočítaly znovu)
void create(int target_color, int k, int n, vector<int>& a, int l, int r, const vector<int>& ord, const set<int>& found){
// Reset na Sphinx barvu (rozpojí vše)
fill(a.begin(), a.end(), n);
for (int j = 0; j < n - 1; j++) {
// Kontrola, zda je tento "most" v aktuálním rozsahu binary searche
bool in_range = (j >= l && j <= r);
// Pokud už jsme tento bod našli, v experimentu ho ignorujeme (necháme Sphinx),
// aby neovlivňoval počty pro hledání dalších.
if (found.count(j)) in_range = false;
if (j % 3 == k) {
// Checkujeme dvojici: ord[j] (Original) -- ord[j+1] (Target Color)
// Pokud ord[j] má barvu 'target_color', spojí se s ord[j+1].
// Nastavíme jen pokud jsme v rozsahu
if (in_range) {
a[ord[j]] = -1; // Original
a[ord[j+1]] = target_color; // Fixed color
}
}
}
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
int n = N;
vector<vector<int>> graf(n);
for (int i = 0; i < X.size(); i++) {
graf[X[i]].push_back(Y[i]);
graf[Y[i]].push_back(X[i]);
}
// 1. Linearizace cesty (seřazení vrcholů, abychom mohli používat j % 3)
vector<int> ord;
{
int start = 0;
for(int i=0; i<n; i++) if(graf[i].size() == 1) { start = i; break; }
vector<bool> vis(n, false);
int curr = start;
while(true){
vis[curr] = true;
ord.push_back(curr);
bool moved = false;
for(int next : graf[curr]){
if(!vis[next]){
curr = next;
moved = true;
break;
}
}
if(!moved) break;
}
}
vector<int> colors(n, -1);
vector<int> a(n);
int identified_count = 0;
// Iterujeme možné barvy.
// Pokud je N velké, spoléháme na to, že součet výskytů všech barev je N,
// takže celkový počet kroků BS bude N*logN.
for (int i = 0; i < n; i++) {
if (identified_count == n) break; // Optimalizace
for (int k = 0; k < 3; k++) {
set<int> found;
// Lambda funkce pro zjištění počtu spojení v intervalu
auto get_matches = [&](int l, int r) {
create(i, k, n, a, l, r, ord, found);
int components = perform_experiment(a);
// Spočítáme, kolik dvojic jsme aktivovali
int active_pairs = 0;
for(int j=l; j<=r; j++) {
if (j % 3 == k && !found.count(j) && j < n-1) active_pairs++;
}
// Každý aktivní pár přidá 2 vrcholy.
// Pokud se NESPOJÍ, přispějí 2 komponentami (nebo 1+1).
// Pokud se SPOJÍ, počet komponent klesne o 1 oproti očekávání.
// Ostatní (Sphinx) jsou izolované komponenty.
// Celkem vrcholů = N. Sphinx = N - 2*active.
// Expected components (pokud žádná shoda) = (N - 2*active) + 2*active = N.
// Každé spojení sníží počet komponent
