#include "sphinx.h"
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
vector <ll> adj[250], V[250];
vector <int> E;
bool visited[250], B[250];
ll n, deg[250], s, mn, k, G[250], mex[250];
vector <int> F;
void dfs(ll u) {
if ((ll)adj[u].size() >= k) return;
for (int i=0; i<n; ++i) mex[i] = -1;
for (auto v : adj[u]) {
if (G[v] != -1) mex[G[v]] = 1;
}
for (int i=0; i<n; ++i) {
if (mex[i] == -1) {
G[u] = i;
break;
}
}
for (auto v : adj[u]) {
if (G[v] == -1) dfs(v);
}
}
void color(ll u) {
for (int i=0; i<n; ++i) E[i] = u;
}
void dfs2(ll u) {
visited[u] = 1;
if (E[u] == -1) return;
for (auto v : adj[u]) {
if (!visited[v] && E[u] == E[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]) dfs2(i), ++tot;
}
return tot;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
for (int i=0; i<N; ++i) adj[i].clear(), V[i].clear(), deg[i] = B[i] = 0, G[i] = -1;
n = N;
F.resize(n);
E.clear();
for (int i=0; i<n; ++i) E.push_back(0);
for (int i=0; i<X.size(); ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i=0; i<n; ++i) {
++deg[(ll)adj[i].size()-1];
}
s = 0, mn = 1e18, k = -1;
for (ll i=0; i<n; ++i) {
s += deg[i];
ll cur = s * (i+1) + (n-s) * n / (i+2);
if (cur < mn) mn = cur, k = i+2;
}
for (int i=0; i<n; ++i) {
if ((ll)adj[i].size() < k) {
if (G[i] == -1) dfs(i);
V[G[i]].push_back(i);
}
else {
ll l, r, mid;
for (int c=0; c<n; c+=(ll)adj[i].size()) {
color(n);
ll x = 0;
E[i] = -1;
for (int j=c; j<min(n, c+(ll)adj[i].size()); ++j) {
E[adj[i][x++]] = j;
}
ll res = perform_experiment(E);
if (res != count()) {
l = c, r = min(n, c+(ll)adj[i].size())-1;
break;
}
}
while (l < r) {
mid = (l+r)/2;
color(n);
ll x = 0;
E[i] = -1;
for (int j=l; j<=mid; ++j) E[adj[i][x++]] = j;
ll res = perform_experiment(E);
if (res != count()) r = mid;
else l = mid+1;
}
F[i] = l;
}
}
for (int i=0; i<n; ++i) {
if (V[i].empty()) continue;
for (int j=0; j<n; ++j) {
while (true) {
color(j);
for (auto u : V[i]) E[u] = (B[u] ? n : -1);
ll res = perform_experiment(E);
if (res == count()) break;
ll l = 0, r = V[i].size()-1, mid;
while (l < r) {
mid = (l+r)/2;
color(j);
for (int x=l; x<=mid; ++x) E[V[i][x]] = (B[V[i][x]] ? n : -1);
res = perform_experiment(E);
if (res != count()) r = mid;
else l = mid+1;
}
F[V[i][l]] = j;
B[V[i][l]] = 1;
}
}
}
return F;
}
