#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
static int N;
static int p[250];
static vector<int> edge[250];
static vector<int> ord;
static bool reached[250];
static set<int> unchecked_set;
static bool keepv[250];
static set<int> ccEdge[250];
static set<int> ccset;
static int parityv[250];
static int where(int x) {
if (p[x] < 0) return x;
return (p[x] = where(p[x]));
}
static int color_id(int x) {
return (ord[x] >= 0 ? ord[x] + N : where(x));
}
static void dfs(int x) {
reached[x] = true;
for (int i : edge[x]) {
if (!reached[i] && color_id(x) == color_id(i)) dfs(i);
}
}
static int expected() {
for (int i = 0; i < N; i++) reached[i] = false;
int sum = 0;
for (int i = 0; i < N; i++) {
if (!reached[i]) {
sum++;
dfs(i);
}
}
return sum;
}
static void pDfs(int x) {
reached[x] = true;
for (int i : ccEdge[x]) {
if (!reached[i]) {
parityv[i] = 1 - parityv[x];
pDfs(i);
}
}
}
vector<int> find_colours(int NN, vector<int> X, vector<int> Y) {
N = NN;
ord.assign(N, -1);
for (int i = 0; i < 250; i++) {
edge[i].clear();
ccEdge[i].clear();
reached[i] = false;
parityv[i] = 0;
keepv[i] = false;
p[i] = -1;
}
unchecked_set.clear();
ccset.clear();
int M = (int)X.size();
for (int i = 0; i < M; i++) {
edge[Y[i]].push_back(X[i]);
edge[X[i]].push_back(Y[i]);
}
for (int i = 1; i < N; i++) {
while (true) {
for (int j = 0; j <= i; j++) ord[j] = -1;
for (int j = i + 1; j < N; j++) ord[j] = N;
if (perform_experiment(ord) == expected()) break;
unchecked_set.clear();
for (int j = 0; j < i; j++) {
if (where(j) != i) unchecked_set.insert(where(j));
}
vector<int> vec;
vec.reserve(unchecked_set.size());
for (int j : unchecked_set) vec.push_back(j);
int a = 0, b = (int)vec.size() - 1;
while (a != b) {
int half = (a + b) / 2;
for (int j = 0; j < N; j++) keepv[j] = false;
for (int j = a; j <= half; j++) keepv[vec[j]] = true;
for (int j = 0; j < i; j++) {
if (keepv[where(j)]) ord[j] = -1;
else ord[j] = N;
}
ord[i] = -1;
for (int j = i + 1; j < N; j++) ord[j] = N;
if (perform_experiment(ord) == expected()) a = half + 1;
else b = half;
}
p[where(vec[a])] = i;
}
}
for (int i = 0; i < N; i++) ccset.insert(where(i));
vector<int> F(N, -1);
if (ccset.size() == 1) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) ord[j] = -1;
ord[0] = i;
if (perform_experiment(ord) == 1) {
for (int j = 0; j < N; j++) F[j] = i;
break;
}
}
} else {
for (int i = 0; i < N; i++) {
for (int j : edge[i]) {
int a = where(i), b = where(j);
if (a != b) {
ccEdge[a].insert(b);
ccEdge[b].insert(a);
}
}
}
for (int i = 0; i < N; i++) reached[i] = false;
int root = *ccset.begin();
parityv[root] = 0;
pDfs(root);
for (int par = 0; par < 2; par++) {
for (int i = 0; i < N; i++) {
while (true) {
for (int j = 0; j < N; j++) {
int w = where(j);
if (parityv[w] == par || F[w] != -1) ord[j] = i;
else ord[j] = -1;
}
if (perform_experiment(ord) == expected()) break;
unchecked_set.clear();
for (int j = 0; j < N; j++) {
int w = where(j);
if (parityv[w] == 1 - par && F[w] == -1) unchecked_set.insert(w);
}
vector<int> vec;
vec.reserve(unchecked_set.size());
for (int j : unchecked_set) vec.push_back(j);
int a = 0, b = (int)vec.size() - 1;
while (a != b) {
int half = (a + b) / 2;
for (int j = 0; j < N; j++) keepv[j] = false;
for (int j = a; j <= half; j++) {
if (F[vec[j]] == -1) keepv[vec[j]] = true;
}
for (int j = 0; j < N; j++) {
if (keepv[where(j)]) ord[j] = -1;
else ord[j] = i;
}
if (perform_experiment(ord) == expected()) a = half + 1;
else b = half;
}
F[where(vec[a])] = i;
}
}
}
for (int i = 0; i < N; i++) F[i] = F[where(i)];
}
return F;
}
