#include <vector>
#include <numeric>
#include <cassert>
#include <algorithm>
using namespace std;
int perform_experiment(vector<int> E);
vector<int> g[250], ng[250];
int P[250], Q[250], c, n;
int fa[250];
int getf(int x) {
return x == fa[x] ? x : fa[x] = getf(fa[x]);
}
// count all components with sphinx's color
int sphinx_components(const vector<int> &Q) {
int res = 0;
iota(fa, fa + n, 0);
for (int i = 0; i < n; i ++) if (Q[i] == n) {
++ res;
for (auto j: g[i]) if (Q[i] == Q[j]) {
int u = getf(i), v = getf(j);
if (u != v)
-- res, fa[u] = v;
}
}
return res;
}
// assume that all groups of -1 are different from their sublings
// count components other than -1
int assume_components(const vector<int> &Q) {
int res = n - count(Q.begin(), Q.end(), -1);
iota(fa, fa + n, 0);
for (int i = 0; i < n; i ++) if (Q[i] != -1)
for (auto j: g[i]) if (Q[i] == Q[j]) {
int u = getf(i), v = getf(j);
if (u != v)
-- res, fa[u] = v;
}
return res;
}
bool check_ng(const vector<int> &v, int l, int r, int col) {
vector<int> query(n);
vector<bool> app(c);
for (int i = l; i <= r; i ++)
app[v[i]] = true;
for (int i = 0; i < n; i ++)
query[i] = (app[P[i]] ? -1 : col);
return perform_experiment(query) != assume_components(query) + (r - l + 1);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
int m = X.size(); n = N;
for (int i = 0; i < m; i ++) {
int x = X[i], y = Y[i];
g[x].push_back(y);
g[y].push_back(x);
}
iota(P, P + n, 0);
fill(Q, Q + n, -1);
// coloring
for (int x = 0; x < n; x ++) {
vector<int> adj_colors;
for (auto v: g[x])
if (v < x)
adj_colors.push_back(P[v]);
sort(adj_colors.begin(), adj_colors.end());
adj_colors.erase(unique(adj_colors.begin(), adj_colors.end()), adj_colors.end());
int L = 0, m = adj_colors.size();
auto check = [&] (int l, int r) {
vector<bool> app(n);
for (int i = l; i <= r; i ++)
app[adj_colors[i]] = true;
vector<int> query(n, n);
query[x] = -1;
for (int i = 0; i < n; i ++) if (P[i] != -1 && app[P[i]])
query[i] = -1;
return sphinx_components(query) + (r - l + 1) + 1 != perform_experiment(query);
};
while (L < m && check(L, m - 1)) {
int l = L, r = m - 1, rl = m - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(L, mid))
rl = mid, r = mid - 1;
else
l = mid + 1;
}
for (int i = 0; i < n; i ++) if (P[i] == adj_colors[rl])
P[i] = x;
L = rl + 1;
}
}
// renumber colors
{
vector<int> G;
for (int i = 0; i < n; i ++)
G.push_back(P[i]);
sort(G.begin(), G.end());
G.erase(unique(G.begin(), G.end()), G.end());
c = G.size();
for (int i = 0; i < n; i ++)
P[i] = lower_bound(G.begin(), G.end(), P[i]) - G.begin();
}
// all with same color
if (c == 1) {
for (int i = 0; i < n; i ++) {
vector<int> query(n, -1);
query[0] = i;
if (perform_experiment(query) == 1)
return vector<int>(n, i);
}
assert(false);
}
for (int i = 0; i < n; i ++)
for (auto j: g[i])
ng[P[i]].push_back(P[j]), ng[P[j]].push_back(P[i]);
vector<int> black, white;
vector<bool> vis(n);
auto dfs = [&] (auto self, int x, int col) -> void {
(col ? black : white).push_back(x);
vis[x] = true;
for (auto y: ng[x]) if (!vis[y])
self(self, y, !col);
};
dfs(dfs, 0, 0);
for (auto v: {black, white}) {
for (int i = 0; i < n; i ++) {
int L = 0;
vector<int> new_v;
for (auto e: v) if (Q[e] == -1)
new_v.push_back(e);
swap(v, new_v);
int m = v.size();
while (L < m && check_ng(v, L, m - 1, i)) {
int l = L, r = m - 1, rl = m - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (check_ng(v, L, mid, i))
rl = mid, r = mid - 1;
else
l = mid + 1;
}
Q[v[rl]] = i;
L = rl + 1;
}
}
}
vector<int> ans(n);
for (int i = 0; i < n; i ++)
ans[i] = Q[P[i]];
return ans;
}