#include "sphinx.h"
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
vector <int> E;
map <ll, ll> mp;
vector <ll> adj[250];
bool visited[250], C[250][250];
ll n, P[250], X[250], ty[250];
ll dsu(ll u) {
if (P[u] == u) return u;
else return P[u] = dsu(P[u]);
}
void color(ll u) {
for (int i=0; i<n; ++i) E[i] = u;
}
void dfs(ll u, ll w) {
ty[u] = w;
for (auto v : adj[u]) {
if (X[v] == -1) {
if (!w) X[u] = v, X[v] = u;
else X[v] = u;
dfs(v, w^1);
}
}
}
void dfs2(ll u) {
visited[u] = 1;
for (auto v : adj[u]) {
if (!visited[v] && E[u] == E[v] && (E[u] != -1 || dsu(u) == dsu(v))) dfs2(v);
}
}
ll count() {
ll tot = 0;
for (int i=0; i<n; ++i) visited[i] = 0;
for (int i=0; i<n; ++i) {
if (!visited[i]) {
++tot;
visited[i] = 1;
if (E[i] != -1) dfs2(i);
}
}
return tot;
}
std::vector<int> find_colours(int N, std::vector<int> ex, std::vector<int> ey) {
n = N;
vector <int> F;
F.resize(n);
E.resize(n);
for (int i=0; i<n; ++i) P[i] = i, ty[i] = X[i] = F[i] = -1;
for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) C[i][j] = 0;
for (int i=0; i<ex.size(); ++i) {
adj[ex[i]].push_back(ey[i]);
adj[ey[i]].push_back(ex[i]);
C[ex[i]][ey[i]] = C[ey[i]][ex[i]] = 1;
}
for (int i=1; i<n; ++i) {
mp.clear();
for (int j=0; j<i; ++j) {
if (C[j][i]) mp[dsu(j)] = j;
}
if (mp.empty()) continue;
vector <ll> V;
for (auto [x, y] : mp) V.push_back(y);
while (!V.empty()) {
color(n);
E[i] = -1;
for (auto u : V) E[u] = -1;
if (perform_experiment(E) == count()) break;
ll l = 0, r = (ll)V.size()-1, mid;
while (l < r) {
mid = (l+r)/2;
color(n);
E[i] = -1;
for (int x=l; x<=mid; ++x) E[V[x]] = -1;
if (perform_experiment(E) == count()) l = mid+1;
else r = mid;
}
P[dsu(V[l])] = dsu(i);
swap(V[l], V[(ll)V.size()-1]);
V.pop_back();
}
}
dfs(0, 0);
vector <ll> V[2];
for (int i=0; i<n; ++i) {
if (dsu(i) == i) {
V[ty[i]].push_back(i);
}
}
for (int x=0; x<2; ++x) {
for (int c=0; c<n; ++c) {
while (!V[x].empty()) {
color(n);
for (auto u : V[x]) E[u] = -1, E[X[u]] = c;
if (perform_experiment(E) == count()) break;
ll l = 0, r = (ll)V[x].size()-1, mid;
while (l < r) {
mid = (l+r)/2;
color(n);
for (int i=l; i<=mid; ++i) E[V[x][i]] = -1, E[X[V[x][i]]] = c;
if (perform_experiment(E) == count()) l = mid+1;
else r = mid;
}
F[V[x][l]] = c;
swap(V[x][l], V[x][(ll)V[x].size()-1]);
V[x].pop_back();
}
}
}
for (int i=0; i<n; ++i) {
if (F[i] == -1) F[i] = F[dsu(i)];
}
return F;
}
