#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 = 0;
stack<int> st;
for (int i = 0; i < N; ++i) vis[i] = false;
for (int i = 0; i < N; ++i) {
if (!vis[i]) {
cnt++;
st.push(i);
while (st.size()) {
int v = st.top();
vis[v] = true;
bool added = false;
for (auto& u : adj[v]) {
if (vis[u]) continue;
if (color(u) != color(v)) continue;
added = true;
st.push(u);
break;
}
if (!added) {
st.pop();
}
}
}
}
return cnt;
}
void get_parity() {
stack<int> st;
for (int i = 0; i < N; ++i) vis[i] = false;
for (int i = 0; i < N; ++i) {
if (!vis[i]) {
st.push(i);
while (st.size()) {
int v = st.top();
vis[v] = true;
bool added = false;
for (auto& u : adj1[v]) {
if (vis[u]) continue;
added = true;
st.push(u);
parity[u] = parity[v] ^ 1;
break;
}
if (!added) {
st.pop();
}
}
}
}
}
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 i = 1; i < N; ++i) {
while (true) {
for (int j = 0; j <= i; ++j) E[j] = -1;
for (int j = i + 1; j < N; ++j) E[j] = N;
// cerr << "Checking if there are no vertices with the same color as " << i << "\n";
if (expected() == perform_experiment(E)) {
break;
}
// cerr << "NOW CHECKING: [0, " << i - 1 << "], with vertice at: " << i << endl;
// must be at least one vertice same color as i
set<int> st;
vector<int> pool;
st.clear();
for (int j = 0; j < i; ++j) {
if (get(j) != i) {
st.insert(get(j));
}
}
pool.clear();
while (st.size()) {
pool.push_back(*begin(st));
st.erase(begin(st));
}
assert((int)pool.size() > 0);
for (auto& u : pool) {
assert(get(u) == u);
}
// cerr << "POOL = ";
// for (auto& u : pool) {
// cerr << u << " ";
// }
// cerr << "\n";
int left = 0, right = (int)pool.size() - 1;
while (left < right) {
// cerr << "[" << left << ", " << right << "]\n";
int mid = (left + right) / 2;
for (int j = 0; j < N; ++j) {
online[j] = false;
}
assert(mid >= 0);
for (int j = 0; j <= mid; ++j) {
online[pool[j]] = 1;
}
for (int j = 0; j < i; ++j) {
if (online[get(j)]) {
E[j] = -1;
} else {
E[j] = N;
}
}
E[i] = -1;
// repetitive?
for (int j = i + 1; j < N; ++j) {
E[j] = N;
}
// cerr << "Starting experiment... -> ";
if (expected() == perform_experiment(E)) {
left = mid + 1;
} else {
right = mid;
}
// cerr << "Finished, with = [" << left << ", " << right << "]\n";
}
// cerr << "Found parent for = " << get(pool[right]) << ", the parent is = " << i << "\n";
assert(get(pool[right]) != i);
p[get(pool[right])] = i;
}
}
set<int> supernodes;
for (int i = 0; i < N; ++i) {
supernodes.insert(get(i));
}
if (supernodes.size() == 1) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
E[j] = i;
}
E[0] = -1;
if (perform_experiment(E) == 1) {
for (int j = 0; j < N; ++j) {
F[j] = i;
}
break;
}
}
} else {
for (int i = 0; i < N; ++i) {
for (auto& u : adj[i]) {
if (get(u) == get(i)) continue;
adj1[get(u)].push_back(get(i));
adj1[get(i)].push_back(get(u));
}
}
get_parity();
for (int i = 0; i < N; ++i) {
cerr << parity[get(i)] << " ";
}
cerr << "\n";
// subtask 3 but on a tree
for (int par = 0; par < 2; ++par) {
for (int i = 0; i < N; ++i) {
while (true) {
for (int j = 0; j < N; ++j) {
if (F[get(j)] != -1 || parity[get(j)] == par) {
E[j] = i;
} else {
E[j] = -1;
}
}
cerr << "Checking color " << i << " for parity " << par << ": ";
for (auto u : E) {
cerr << u << " ";
}
cerr << "\n";
if (expected() == perform_experiment(E)) {
break;
}
set<int> st;
vector<int> pool;
for (int j = 0; j < N; ++j) {
if (parity[get(j)] == par ^ 1 && F[get(j)] == -1) {
st.insert(get(j));
}
}
while (st.size()) {
pool.push_back(*begin(st));
st.erase(begin(st));
}
int left = 0, right = (int)pool.size() - 1;
cerr << "Pool: ";
for (auto& u : pool) {
cerr << u << " ";
}
cerr << "\n";
while (left < right) {
int mid = (left + right) / 2;
for (int j = 0; j < N; ++j) online[j] = false;
for (int j = 0; j <= mid; ++j) {
online[pool[j]] = true;
}
for (int j = 0; j < N; ++j) {
if (online[get(j)]) {
E[j] = -1;
} else {
E[j] = i;
}
}
if (expected() == perform_experiment(E)) {
left = mid + 1;
} else {
right = mid;
}
}
F[pool[right]] = i;
}
}
}
}
for (int i = 0; i < N; ++i) {
F[i] = F[get(i)];
}
return F;
}
