#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n,g[N][N],fa[N],Fa[N];
int find(int x){return (fa[x]==x?x:fa[x]=find(fa[x]));}
int Find(int x){return (Fa[x]==x?x:Fa[x]=Find(Fa[x]));}
void merge(int x,int y){fa[find(x)]=find(y);}
void Merge(int x,int y){Fa[Find(x)]=Find(y);}
vector<int> node[N];
int calc(const vector<int>& E){
for(int i=0;i<n;++i) Fa[i]=i;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
if(E[i]==n && E[j]==n && g[i][j]==1) Merge(i,j);
}
}
int ans=0;
for(int i=0;i<n;++i){
if(E[i]==n && Fa[i]==i) ++ans;
}
return ans;
}
vector<int> find_colours(int nn,vector<int> X,vector<int> Y){
n=nn;
memset(g,0,sizeof(g));
for(int i=0;i<(int)X.size();++i) g[X[i]][Y[i]]=g[Y[i]][X[i]]=1;
for(int i=0;i<n;++i) fa[i]=i;
for(int u=0;u<n;++u){
vector<int> E(n,-1);
for(int v=0;v<n;++v){
if((v>u || g[u][v]==0) && u!=v) E[v]=n;
}
int tar=0;
for(int i=0;i<n;++i){
if(fa[i]==i && E[i]!=n) ++tar;
}
if(perform_experiment(E)==tar+calc(E)) continue;
while(true){
for(int i=0;i<n;++i) node[i].clear();
vector<int> vev;
for(int i=0;i<n;++i) node[find(i)].push_back(i);
for(int i=0;i<n;++i){
if(i==find(u)) continue;
for(int x:node[i]){
if(x<=u && g[u][x]==1){
vev.push_back(i);
break;
}
}
}
int l=0,r=(int)vev.size(),ans=-1;
while(l<r){
int mid=l+(r-l)/2;
vector<int> F(n,n);
for(int j=mid;j<(int)vev.size();++j){
for(int x:node[vev[j]]) F[x]=-1;
}
F[u]=-1;
if(perform_experiment(F)==(int)vev.size()-mid+1+calc(F)) r=mid;
else{
ans=mid;
l=mid+1;
}
}
assert(ans!=-1);
merge(u,vev[ans]);
tar=0;
for(int i=0;i<n;++i){
if(fa[i]==i && E[i]!=n) ++tar;
}
if(perform_experiment(E)==tar+calc(E)) break;
}
}
#ifndef HHY
vector<int> res(n);
int tot=0;
for(int i=0;i<n;++i){
if(fa[i]==i) res[i]=tot++;
}
for(int i=0;i<n;++i) res[i]=res[find(i)];
return res;
#endif
}