#include<bits/stdc++.h>
#define MAXN 307
#include "sphinx.h"
using namespace std;
int n,m,in[MAXN];
vector<int> v[MAXN],subtree[MAXN];
bool connected[MAXN][MAXN],vis[MAXN];
int color[MAXN];
struct unionfind{
int dsu[MAXN];
void init(){
for(int i=1;i<=n;i++)dsu[i]=i;
}
int root(int x){
if(dsu[x]==x)return dsu[x];
dsu[x]=root(dsu[x]);
return dsu[x];
}
void mergev(int x,int y){
dsu[root(x)]=root(y);
}
bool conn(int x,int y){
return root(x)==root(y);
}
}graph;
void dfs2(int x){
vis[x]=true;
for(int i:v[x]){
if(!vis[i] and color[i]==color[x] and color[i]!=-1)dfs2(i);
}
}
int calc_comps(){
for(int i=1;i<=n;i++)vis[i]=false;
int res=0;
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs2(i); res++;
}
}
return res;
}
int experiment(){
vector<int> e;
for(int i=1;i<=n;i++)e.push_back(color[i]);
return perform_experiment(e);
}
void findcolor(int x,vector<int> c){
for(int i=1;i<=n;i++)color[i]=n;
for(int i:c)color[i]=-1;
color[x]=-1;
int l=-1,r=c.size(),tt;
while(l+1<r){
tt=(l+r)/2;
for(int f:c)color[f]=n;
for(int f=0;f<=tt;f++)color[c[f]]=-1;
int comps=calc_comps();
if(experiment()<comps){
r=tt;
}else{
l=tt;
}
}
if(r!=c.size())graph.mergev(x,c[r]);
}
void dfs(int x,int p){
in[x]=1;
subtree[x]={x};
vector<int> children;
for(int i:v[x]){
if(in[i]==0){
dfs(i,x);
children.push_back(i);
for(int f:subtree[i])subtree[x].push_back(f);
}
}
for(int i:children){
vector<int> c;
for(int f:subtree[i]){
if(!connected[f][x])continue;
bool bad=false;
for(int k:c){
if(graph.conn(k,f))bad=true;
}
if(!bad)c.push_back(f);
}
findcolor(x,c);
}
in[x]=2;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
n=N; m=int(X.size());
for(int i=1;i<=m;i++){
v[X[i-1]+1].push_back(Y[i-1]+1);
v[Y[i-1]+1].push_back(X[i-1]+1);
connected[X[i-1]+1][Y[i-1]+1]=true;
connected[Y[i-1]+1][X[i-1]+1]=true;
}
graph.init();
dfs(1,0);
vector<int> ans;
for(int i=1;i<=n;i++){
ans.push_back(graph.root(i)-1);
}
return ans;
}
