#include "sphinx.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
#include <bits/stdc++.h>
using namespace std;
vector<int> find_colours(int N,
vector<int> X,
vector<int> Y)
{
// (You can omit the DSU‐on‐edges pre‑step if you like —
// it doesn’t change the asymptotic experiment count.)
// Phase 2: bitwise recovery of each C[i]
int B = 0;
while ((1 << B) < N)
++B; // number of bits needed
vector<int> recovered(N, 0), E(N);
// For each bit, determine which vertices have that bit = 1
for (int b = 0; b < B; ++b)
{
// Build E so that:
// - if we want to “test” vertex i for bit b = 1, set E[i] = -1
// (so vertex i keeps its original colour C[i]),
// - otherwise set E[i] = N (the Sphinx’s colour).
//
// After recolouring, the Sphinx‐coloured vertices (those with E[i]=N)
// form exactly one connected component (since the original graph
// is connected and we gave them all the same colour). Each vertex
// for which E[i] = -1 becomes its own singleton component unless
// its original bit‑b = 1, in which case it merges into the Sphinx
// component (because then its recoloured colour = Sphinx’s colour
// for this experiment).
//
// Thus the total #components = 1 (the big Sphinx blob of all i with
// bit‑b=1) + (# of i with bit‑b=0). We therefore can infer, for
// each i, whether bit‑b of C[i] = 1 by seeing if flipping E[i]
// from N to –1 *decreases* the component count by 1.
// first, set E[i]=N for all i
fill(E.begin(), E.end(), N);
int base = perform_experiment(E);
// base = 1 + (# vertices whose bit‑b = 0)
// now test each i individually
for (int i = 0; i < N; ++i)
{
// “unmask” i
E[i] = -1;
int comps = perform_experiment(E);
// if C[i] has bit b = 1, then giving it original colour
// means it joins the big Sphinx blob ⇒ comps = base − 1
// otherwise it stays its own singleton ⇒ comps = base + 0
if (comps == base - 1)
{
recovered[i] |= (1 << b);
}
// restore
E[i] = N;
}
}
return recovered;
}
