#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 250;
int n;
vector<int> g[MXN], G;
namespace comp_cnt {
vector<int> E;
bool vis[MXN];
void dfs(int v) {
vis[v] = 1;
for(int u : g[v])
if(!vis[u] && E[v]==E[u] && (E[v]!=-1 || G[v]==G[u]))
dfs(u);
}
int get(vector<int> E) {
comp_cnt::E = E;
fill(vis, vis+n, 0);
int res=0;
for(int i=0; i<n; i++)
if(!vis[i]) {
dfs(i);
res++;
}
return res;
}
}
namespace component {
int timer=-1;
bool mark[MXN], vis[MXN];
int find_leaf(int v) {
vis[v] = 1;
for(int u : g[v])
if(!mark[u] && !vis[u])
return find_leaf(u);
return v;
}
void solve() {
int cnt=0, v=-1;
for(int i=0; i<n; i++)
if(!mark[i]) {
vis[i] = 0;
v = i;
cnt++;
}
if(cnt==1) {
G[v] = ++timer;
return;
}
v = find_leaf(v);
mark[v] = 1;
solve();
mark[v] = 0;
vector<int> E(n, -1);
for(int v=0; v<n; v++)
if(mark[v])
E[v] = n;
if(perform_experiment(E)==comp_cnt::get(E)) {
G[v] = ++timer;
return;
}
int l=-1, r=timer, mid;
while(r-l>1) {
mid = (l+r)>>1;
for(int v=0; v<n; v++)
if(!mark[v])
E[v] = (G[v]<=mid ? -1 : n);
(perform_experiment(E)==comp_cnt::get(E) ? l : r) = mid;
}
G[v] = r;
}
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
n = N;
G.resize(n, -1);
for(int i=0; i<X.size(); i++)
g[X[i]].push_back(Y[i]),
g[Y[i]].push_back(X[i]);
component::solve();
return G;
}
