#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;

int N,M,fa[260];
vector<int> ans;
vector<int> ed[260],E[260],con,cc;
vector<int> nd[260];
vector<int> tk;
vector<int> col[2];
bool vis[260];
int get_fa(int a){return a==fa[a]?a:fa[a]=get_fa(fa[a]);}
void merge(int u,int v)
{
	u=get_fa(u),v=get_fa(v);
	fa[v]=u;
	for(int g:nd[v]) nd[u].push_back(g);
}

void dfs(int a,int col)
{
	::col[col].push_back(a),vis[a]=true;
	for(int g:ed[a]) if(!vis[g])
		dfs(g,col^1);
}
void ddfs(int a)
{
	vis[a]=true;
	for(int g:ed[a]) if(!vis[g])
		ddfs(g);
}

int calc_n(int l,int r,int x)
{
	int ret=r-l+1+1;
	memset(vis,0,sizeof(vis));
	for(int i=l;i<=r;i++) for(int g:nd[con[i]]) vis[g]=true;
	vis[x]=true;
	for(int i=0;i<N;i++) if(!vis[i])
		ret++,ddfs(i);
	return ret;
}
int Qry1(int l,int r,int x)
{
	for(int i=0;i<N;i++) tk[i]=N;
	for(int i=l;i<=r;i++) for(int g:nd[con[i]]) tk[g]=-1;
	tk[x]=-1;
	return perform_experiment(tk);
}

int calc_nm(vector<int> &num,int l,int r)
{
	int ret=r-l+1;
	memset(vis,0,sizeof(vis));
	for(int i=l;i<=r;i++) vis[num[i]]=true;
	for(int i=0;i<N;i++) if(i==get_fa(i)&&!vis[i])
		ret++,ddfs(i);
	return ret;
}
int Qry2(int c,vector<int> &num,int l,int r)
{
	for(int i=0;i<N;i++) tk[i]=c;
	for(int i=l;i<=r;i++) tk[num[i]]=-1;
	return perform_experiment(tk);
}
void solve(int id)
{
	for(int c=0;c<N;c++)
	while(calc_nm(col[id],0,col[id].size()-1)!=Qry2(c,col[id],0,col[id].size()-1))
	{
		int l=0,r=col[id].size()-1,mid;
		while(l<r)
		{
			mid=(l+r>>1);
			if(calc_nm(col[id],l,mid)!=Qry2(c,col[id],l,mid)) r=mid;
			else l=mid+1;
		}
		ans[col[id][l]]=c;
		col[id].erase(col[id].begin()+l);
	}
}

vector<int> find_colours(int N,vector<int> X,vector<int> Y)
{
	::N=N;
	ans.resize(N),M=X.size(),tk.resize(N);

	for(int i=0;i<M;i++)
	{
		if(X[i]>Y[i]) E[X[i]].push_back(Y[i]);
		else E[Y[i]].push_back(X[i]);
		ed[X[i]].push_back(Y[i]);
		ed[Y[i]].push_back(X[i]);
	}

	for(int i=0;i<N;i++)
	{
		vector<int>().swap(con),vector<int>().swap(cc);
		fa[i]=i,nd[i].push_back(i);

		for(int g:E[i]) con.push_back(get_fa(g));
		sort(con.begin(),con.end());con.erase(unique(con.begin(),con.end()),con.end());

		while(Qry1(0,con.size()-1,i)!=calc_n(0,con.size()-1,i))
		{
			int l=0,r=con.size()-1,mid;
			while(l<r)
			{
				mid=(l+r>>1);
				if(Qry1(l,mid,i)!=calc_n(l,mid,i)) r=mid;
				else l=mid+1;
			}
			cc.push_back(con[l]);
			con.erase(con.begin()+l);
		}
		for(int g:cc) merge(i,g);
	}

	int tot=0;
	for(int i=0;i<N;i++) tot+=(i==get_fa(i));

	if(tot==1)
	{
		for(int i=0;i<N;i++) tk[i]=-1;
		for(int c=0;c<N;c++)
		{
			tk[0]=c;
			if(perform_experiment(tk)==1)
			{
				for(int i=0;i<N;i++) ans[i]=c;
				return ans;
			}
		}
	}

	for(int i=0;i<N;i++) vector<int>().swap(ed[i]);
	for(int i=0,x,y;i<M;i++)
	{
		x=get_fa(X[i]),y=get_fa(Y[i]);
		if(x!=y) ed[x].push_back(y),ed[y].push_back(x);
	}
	for(int i=0;i<N;i++)
	{
		sort(ed[i].begin(),ed[i].end());
		ed[i].erase(unique(ed[i].begin(),ed[i].end()),ed[i].end());
	}

	memset(vis,0,sizeof(vis));
	dfs(get_fa(0),0);
	solve(0),solve(1);

	for(int i=0;i<N;i++) if(i!=get_fa(i))
		ans[i]=ans[get_fa(i)];
	return ans;
}