#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int NR=210;
int n,m,c[NR],fa[NR],tot,cnt,opt[NR];
vector<int>g[NR];
#define pb emplace_back

void init(){
	for(int i=1;i<=n;i++)fa[i]=i;
	cnt=n;
}
int get(int x){
	if(fa[x]==x)return x;
	return fa[x]=get(fa[x]);
}
void merge(int x,int y){
	x=get(x);y=get(y);
	if(x==y)return;
	fa[x]=y;cnt--;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
	n=N;m=X.size(); 
	for(int i=0;i<m;i++)g[X[i]+1].pb(Y[i]+1),g[Y[i]+1].pb(X[i]+1);
	for(int i=1;i<=n;i++){
		vector<int>buc;
		for(int x:g[i])
			if(x<i)buc.pb(x);
		if(!buc.size()){
			c[i]=tot++;
			continue;
		}
		int l=0,r=buc.size()-1,res=-1;c[i]=-1;
		sort(buc.begin(),buc.end());
//		printf("i:%d\n",i);
//		for(int x:buc)printf("%d ",x);puts("");
		while(l<=r){
			int mid=(l+r)>>1;init();
			for(int j=1;j<=n;j++)opt[j]=-1;
			for(int j=0;j<=mid;j++)opt[buc[j]]=1;
			opt[i]=1;
			for(int j=1;j<=n;j++)
				for(int x:g[j])
					if(opt[j]==opt[x]){
						if(opt[j]==-1)merge(j,x);
						else if(c[j]==c[x])merge(j,x);
					}
//			printf("mid:%d cnt:%d\n",mid,cnt);
//			for(int j=1;j<=n;j++)printf("%d ",opt[j]);puts("");
//			for(int j=1;j<=n;j++)printf("%d ",get(j));puts("");
			vector<int>arr;
			for(int i=1;i<=n;i++)
				if(opt[i]==-1)arr.pb(n);
				else arr.pb(-1);
			int tmp=perform_experiment(arr);
//			printf("tmp:%d\n",tmp);
			if(tmp!=cnt)res=mid,r=mid-1;
			else l=mid+1; 
		}
		if(res==-1)c[i]=tot++;
		else c[i]=c[buc[res]];
	}
	vector<int>ans;
	for(int i=1;i<=n;i++)ans.pb(c[i]);
	return ans;
}