#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int NR=300;
int n,m,c[NR],fa[NR],tot,cnt,opt[NR],ans[NR],nc[NR],color[NR];
vector<int>g[NR],buc[NR],G[NR],v1,v2;
#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--;
}

void dfs(int id,int k){
	if(color[id])return;
	if(k==1)v1.pb(id);
	else v2.pb(id);
	color[id]=k;
	for(int x:G[id])dfs(x,k^3);
}

bool check(vector<int>idx,vector<int>lcy,int color){
	for(int i=1;i<=n;i++)opt[i]=1;
	for(int x:idx)opt[x]=0;
	init();
	for(int i=1;i<=n;i++)
		for(int x:g[i])
			if(opt[c[x]]==opt[c[i]]){
				if(opt[c[x]])merge(i,x);
				else if(c[i]==c[x])merge(i,x);
			}
	vector<int>arr;
	for(int i=1;i<=n;i++)
		if(opt[c[i]])arr.pb(color);
		else arr.pb(-1);
	int tmp=perform_experiment(arr);
//	printf("---color:%d cnt:%d %d\n",color,cnt,tmp);
//	for(int x:idx)printf("%d ",x);puts("");
//	for(int x:lcy)printf("%d ",x);puts("");
//	for(int i=1;i<=n;i++)printf("%d ",get(i));puts("");
	return cnt!=tmp;
}

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++)c[i]=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())continue;
		sort(buc.begin(),buc.end());
		int L=0,R=buc.size()-1;
		while(L<=R){
			init();
			for(int j=1;j<=n;j++)opt[j]=-1;
			for(int j=L;j<=R;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);
					}
			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);
			if(tmp==cnt)break;
			int l=L,r=R,res=-1;
			while(l<=r){
				int mid=(l+r)>>1;init();
				for(int j=1;j<=n;j++)opt[j]=-1;
				for(int j=L;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);
						}
				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);
				if(tmp!=cnt)res=mid,r=mid-1;
				else l=mid+1; 
			}
			if(res==-1)break;
			else{
				int x=c[buc[res]];
				for(int j=1;j<=n;j++)
					if(c[j]==x)c[j]=i-1;
				L=res+1;
			}
		}
	}
	bool ok=1;
	for(int i=1;i<=n;i++)ok&=(c[i]==n-1);
	if(ok){
		int ans=0;
		for(int c=0;c<n;c++){
			init();
			for(int j=1;j<n;j++)opt[j]=-1;opt[n]=1;
			for(int j=1;j<=n;j++)
				for(int x:g[j])
					if(opt[j]==-1&&opt[x]==-1)merge(j,x);
			vector<int>arr;
			for(int i=1;i<=n;i++)
				if(opt[i]==1)arr.pb(-1);
				else arr.pb(c);
			int tmp=perform_experiment(arr);
			if(tmp!=cnt){
				ans=c;
				break;
			}
		}
		vector<int>arr;
		for(int i=1;i<=n;i++)arr.pb(ans);
		return arr;
	}
	for(int i=1;i<=n;i++)c[i]++,buc[c[i]].pb(i);
	for(int i=1;i<=n;i++)
		for(int x:g[i])if(c[i]!=c[x])G[c[i]].pb(c[x]);
	dfs(n,1);
//	for(int x:v1)printf("%d ",x);puts("");
//	for(int x:v2)printf("%d ",x);puts("");
	for(int i=0;i<n;i++){
		if(check(v1,v2,i)){
//			printf("1:%d\n",i);
			int L=0,R=v1.size()-1;
			while(L<=R){
				vector<int>b1,b2;
				for(int i=0;i<=R;i++)
					if(L<=i&&i<=R)b1.pb(v1[i]);
					else b2.pb(v1[i]);
				for(int x:v2)b2.pb(x);
				if(!check(b1,b2,i))break;
				int l=L,r=R,res=-1;
				while(l<=r){
					int mid=(l+r)>>1;
					vector<int>b1,b2;
					for(int i=0;i<=R;i++)
						if(l<=i&&i<=r)b1.pb(v1[i]);
						else b2.pb(v1[i]);
					for(int x:v2)b2.pb(x);
					if(check(b1,b2,i))res=mid,r=mid;
					else l=mid+1;
				}
				if(res==-1)break;
				else{
					ans[v1[res]]=i;
					L=res+1;
				}
			}
		}
		if(check(v2,v1,i)){
//			printf("2:%d\n",i);
			int L=0,R=v2.size()-1;
			while(L<=R){
				vector<int>b1,b2;
				for(int i=0;i<=R;i++)
					if(L<=i&&i<=R)b2.pb(v2[i]);
					else b1.pb(v2[i]);
				for(int x:v1)b1.pb(x);
				if(!check(b2,b1,i))break;
				int l=L,r=R,res=-1;
				while(l<=r){
					int mid=(l+r)>>1;
					vector<int>b1,b2;
					for(int i=0;i<=R;i++)
						if(l<=i&&i<=r)b2.pb(v2[i]);
						else b1.pb(v2[i]);
					for(int x:v1)b1.pb(x);
					if(check(b2,b1,i))res=mid,r=mid;
					else l=mid+1;
				}
				if(res==-1)break;
				else{
					ans[v2[res]]=i;
					L=res+1;
				}
			}
		}
	}
	vector<int>arr;
	for(int i=1;i<=n;i++)arr.pb(ans[c[i]]);
	return arr;
}