#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> E;
int N;
const int MAXN = 250;
int p[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN];
vector<int> adj1[MAXN];
int parity[MAXN];
int get(int x) {
return (p[x] < 0 ? x : p[x] = get(p[x]));
}
int color(int x) {
return (E[x] >= 0 ? E[x] + N : get(x));
}
int expected() {
int cnt = 1;
for (int i = 1; i < N; ++i) {
if (E[i] != E[i - 1]) {
cnt++;
}
}
return cnt;
}
std::vector<int> find_colours(int _N, std::vector<int> X, std::vector<int> Y) {
N = _N;
E = vector<int>(N);
vector<int> F(N, -1);
vector<bool> online(N);
for (int i = 0; i < (int)X.size(); ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < N; ++i) {
p[i] = -1;
}
for (int par = 0; par < 2; ++par) {
for (int i = 0; i < N; ++i) {
while (true) {
for (int j = 0; j < N; ++j) {
if ((j & 1) == par || F[j] != -1) {
E[j] = i;
} else {
E[j] = -1;
}
}
if (expected() == perform_experiment(E)) {
break;
}
vector<int> pool;
for (int j = 0; j < N; ++j) {
if ((j & 1) == par ^ 1 && F[j] == -1) {
pool.push_back(j);
}
}
int left = 0, right = (int)pool.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
for (int j = 0; j < N; ++j) {
E[j] = i;
}
for (int j = 0; j <= mid; ++j) {
E[pool[j]] = -1;
}
if (expected() == perform_experiment(E)) {
left = mid + 1;
} else {
right = mid;
}
}
F[pool[right]] = i;
}
}
}
return F;
}
