#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) int(x.size())
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++;
}
// cout << res << '\n';
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;
}
// cout << v << ' ';
v = find_leaf(v);
// cout << v << '\n';
mark[v] = 1;
solve();
mark[v] = 0;
// cout << "NOW " << v << '\n';
vector<int> E(n, -1);
for(int i=0; i<n; i++)
if(mark[i])
E[i] = n;
if(perform_experiment(E)==comp_cnt::get(E)) {
G[v] = ++timer;
return;
}
vector<int> vec;
for(int u : g[v])
if(!mark[u])
vec.push_back(u);
int l=-1, r=SZ(vec)-1, mid;
while(r-l>1) {
mid = (l+r)>>1;
for(int i=0; i<=mid; i++) E[vec[i]] = -1;
for(int i=mid+1; i<n; i++) E[vec[i]] = n;
(perform_experiment(E)==comp_cnt::get(E) ? l : r) = mid;
}
G[v] = G[vec[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;
}
