#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
const int MN = 255;
bool deb = false;
void dbg(vector<int> xx) {
if (!deb) return;
cout << "DBG: ";
for (auto x: xx) cout << x << " ";
cout << "\n";
}
int par[MN], sz[MN];
int n, m;
vector<vector<int>> g;
vector<bool> ok;
void init_dsu() {
for (int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
}
int find(int u) {
if (par[u] == u) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
par[u] = v;
sz[v] += sz[u];
}
int ask(vector<bool> act) {
vector<int> col(n);
for (int i = 0; i < n; i++) col[i] = n;
for (int i = 0; i < n; i++) {
if (act[i]) col[i] = -1;
}
int tot = perform_experiment(col);
return tot;
}
vector<bool> vis;
vector<int> cc;
void dfs(int node, int c) {
vis[node] = true;
for (auto next: g[node]) {
if (vis[next] || cc[next] != c) continue;
dfs(next, cc[node]);
}
}
int comps(vector<bool> act) {
vis.assign(n, false);
cc.assign(n, n);
for (int i = 0; i < n; i++) {
if (act[i]) cc[i] = i;
}
int ret = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
dfs(i, cc[i]);
ret++;
}
return ret;
}
int check(int node, vector<int> cand) {
if (cand.empty()) return -1;
vector<bool> act(n, false);
act[node] = true;
for (auto x: cand) act[x] = true;
int tot = ask(act);
dbg({node, tot, comps(act)});
if (tot == comps(act)) return -1;
int lo = 0, hi = (int)cand.size()-1;
int fin = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
act.assign(n, false);
for (int i = 0; i <= mid; i++) act[cand[i]] = true;
act[node] = true;
tot = ask(act);
if (tot == comps(act)) {
lo = mid+1;
}
else {
fin = mid;
hi = mid-1;
}
}
assert(fin != -1);
return cand[fin];
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
n = N;
m = X.size();
g.resize(n);
for (int i = 0; i < m; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
init_dsu();
ok.assign(n, false);
for (int node = 0; node < n; node++) {
ok[node] = true;
while (true) {
vector<int> ch;
set<int> added;
added.insert(find(node));
for (auto next: g[node]) {
if (!ok[next]) continue;
if (added.find(find(next)) == added.end()) {
ch.push_back(next);
added.insert(find(next));
}
}
int ret = check(node, ch);
if (ret == -1) break;
merge(ret, node);
}
}
vector<int> ans;
for (int i = 0; i < n; i++) ans.push_back(find(i));
return ans;
}
