#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];
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++)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());
//		printf("i:%d\n",i);
//		for(int x:buc)printf("%d ",x);puts("");
		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);
					}
//			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);
			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);
						}
	//			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)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;
			}
		}
	}
	for(int i=1;i<=n;i++)
		if(c[i]==i-1){
			vector<int>buc;
			for(int j=1;j<=n;j++)
				if(c[i]==c[j])buc.pb(j);
			set<int>s;
			for(int x:buc)
				for(int y:g[x])
					if(c[y]!=c[i])s.insert(y);
			int k=s.size(),now=0,res=-1,l,r;
//			printf("i:%d\n",i);
			while(now<n-1){
				for(int j=1;j<=n;j++)opt[j]=-1;
				for(int x:buc)opt[x]=1;
				for(int x:s)opt[x]=0;
				init();
				for(int j=1;j<=n;j++)
					for(int x:g[j])
						if(opt[j]==opt[x]&&opt[j]){
							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])arr.pb(min(now++,n-2));
					else if(opt[i]==-1)arr.pb(n);
					else arr.pb(-1);
//				for(int i=0;i<n;i++)cout<<arr[i]<<' ';cout<<endl;
				int tmp=perform_experiment(arr);
//				printf("now:%d k:%d %d %d\n",now,k,cnt,tmp);
				if(tmp!=cnt){
					r=min(now-1,n-2);l=now-k;res=0;
					break;
				}
			}
			if(res==-1)ans[i]=n-1;
			else{
				while(l<r){
					int mid=(l+r)>>1;
					for(int j=1;j<=n;j++)opt[j]=-1;
					for(int x:buc)opt[x]=1;
					for(int x:s)opt[x]=0;
					init();
					for(int j=1;j<=n;j++)
						for(int x:g[j])
							if(opt[j]==opt[x]&&opt[j]){
								if(opt[j]==-1)merge(j,x);
								else if(c[j]==c[x])merge(j,x);
							}
					vector<int>arr;
					int now=l;
					for(int i=1;i<=n;i++)
						if(!opt[i])arr.pb(min(now++,mid));
						else if(opt[i]==-1)arr.pb(n);
						else arr.pb(-1);
					int tmp=perform_experiment(arr);
					if(tmp!=cnt)r=mid;
					else l=mid+1;
				}
				ans[i]=l;
			}
		}
	vector<int>arr;
	for(int i=1;i<=n;i++)arr.pb(ans[c[i]+1]);
	return arr;
}