#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 250;
int n, m;
int vert;
int parent[MAX_N];
vector<int> adj[MAX_N];
mt19937 rnd(1010);
int findParent(int v) {
if (parent[v] != v)
parent[v] = findParent(parent[v]);
return parent[v];
}
void unionn(int u, int v) {
// printf("UNESC %d %d\n", u, v);
u = findParent(u);
v = findParent(v);
if (u == v)
return;
parent[u] = v;
}
int ask(vector<int> v) {
vector<int> e(n, n);
for (int i: v)
e[i] = -1;
e[vert] = -1;
int a = perform_experiment(e);
for (int i: v)
e[i] = 0;
e[vert] = 0;
int b = perform_experiment(e);
return v.size() - a + b;
}
void divide(vector<int> cand, int c) {
shuffle(cand.begin(), cand.end(), rnd);
int n = cand.size();
if (n == 0)
return;
if (c == -1)
c = ask(cand);
if (c == 0)
return;
if (n == 1) {
unionn(vert, cand[0]);
return;
}
vector<int> a, b;
for (int i = 0; i < n / 2; i++)
a.push_back(cand[i]);
for (int i = n / 2; i < n; i++)
b.push_back(cand[i]);
int aa = ask(a);
int bb = c - aa;
if (aa > 0)
divide(a, aa);
if (bb > 0)
divide(b, bb);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
n = N;
m = X.size();
for (int i = 0; i < m; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int v = 0; v < n; v++)
parent[v] = v;
for (int v = 1; v < n; v++) {
vector<int> cand;
set<int> s;
for (int u: adj[v]) {
if (u < v) {
if (s.find(findParent(u)) == s.end()) {
s.insert(findParent(u));
cand.push_back(u);
}
}
}
// printf("CAND ");
// for (int u: cand)
// printf("%d ", u);
// printf("\n");
vert = v;
divide(cand, -1);
}
vector<int> ans(n);
for (int v = 0; v < n; v++)
ans[v] = findParent(v);
return ans;
}
