#include "sphinx.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
vector<int> find_colours(int N,
vector<int> X,
vector<int> Y)
{
// 1) build adjacency list & spanning tree via BFS
vector<vector<int>> adj(N);
for (int j = 0; j < (int)X.size(); j++)
{
adj[X[j]].push_back(Y[j]);
adj[Y[j]].push_back(X[j]);
}
vector<bool> seen(N, false);
vector<pair<int, int>> tree_edges;
queue<int> q;
q.push(0);
seen[0] = true;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v : adj[u])
{
if (!seen[v])
{
seen[v] = true;
tree_edges.emplace_back(u, v);
q.push(v);
}
}
}
// 2) DSU init
vector<int> parent(N);
iota(parent.begin(), parent.end(), 0);
function<int(int)> findp = [&](int u)
{
return parent[u] == u ? u : parent[u] = findp(parent[u]);
};
auto unite = [&](int u, int v)
{
u = findp(u);
v = findp(v);
if (u != v)
parent[v] = u;
};
// 3) for each tree edge, test same‑colour
vector<int> E(N);
for (auto [u, v] : tree_edges)
{
fill(E.begin(), E.end(), N);
E[u] = E[v] = -1;
int comps = perform_experiment(E);
if (comps == 2)
{
// u and v share a colour
unite(u, v);
}
// else they differ, leave them separate
}
// 4) assign each component an arbitrary label 0..K-1
vector<int> comp_id(N, -1), G(N);
int next_label = 0;
for (int i = 0; i < N; i++)
{
int r = findp(i);
if (comp_id[r] < 0)
comp_id[r] = next_label++;
G[i] = comp_id[r];
}
return G;
}
