#include<bits/stdc++.h>
#include "sphinx.h"
using namespace std;
const int MAXN=255;
vector <int> G[MAXN],E[MAXN],R[MAXN];
int n;
struct DSU {
	int dsu[MAXN];
	void init() { iota(dsu,dsu+n,0); }
	int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
	bool merge(int x,int y) {
		x=find(x),y=find(y),dsu[x]=y;
		return x^y;
	}
}	F,T;
int count(const vector<int>&V) {
	static bitset<MAXN> inq;
	inq.reset(),T.init();
	for(int i:V) inq.set(i);
	int s=V.size();
	for(int i:V) for(int j:G[i]) if(inq[j]) s-=T.merge(i,j);
	return s;
}
int col[MAXN];
void solve(vector<int> S) {
	for(int c=0;c<n;++c) {
		vector <int> X;
		while(S.size()) {
			auto chk=[&](int k) {
				vector <int> q(n,c),r;
				for(int i=0;i<=k;++i) for(int u:R[S[i]]) q[u]=-1;
				for(int i=0;i<n;++i) if(~q[i]) r.push_back(i);
				return perform_experiment(q)<count(r)+k+1;
			};
			int l=0,r=S.size()-2,x=S.size()-1;
			if(!chk(x)) {
				X.insert(X.end(),S.begin(),S.end());
				break;
			}
			while(l<=r) {
				int mid=(l+r)>>1;
				if(chk(mid)) x=mid,r=mid-1;
				else l=mid+1;
			}
			col[S[x]]=c;
			X.insert(X.end(),S.begin(),S.begin()+x);
			S.erase(S.begin(),S.begin()+x+1);
		}
		S.swap(X);
	}
}
vector<int> find_colours(int N,vector<int>X,vector<int>Y) {
	n=N,F.init();
	for(int i=0;i<(int)X.size();++i) G[X[i]].push_back(Y[i]),G[Y[i]].push_back(X[i]);
	for(int u=0;u<n;++u) {
		static bitset <MAXN> vis;
		vis.reset();
		vector <int> Ne,C;
		for(int v:G[u]) if(v<u&&!vis[F.find(v)]) {
			Ne.push_back(F.find(v)),vis.set(F.find(v));
		}
		while(Ne.size()) {
			auto chk=[&](int k) { //qry Ne[0,k]
				vector <int> q(n,n),r;
				vis.reset(),q[u]=-1;
				for(int i=0;i<=k;++i) vis.set(Ne[i]);
				for(int i=0;i<u;++i) if(vis[F.find(i)]) q[i]=-1;
				for(int i=0;i<n;++i) if(~q[i]) r.push_back(i);
				int z=perform_experiment(q);
				return count(r)+k+2>z;
			};
			int l=0,r=Ne.size()-2,x=Ne.size()-1;
			if(!chk(x)) break;
			while(l<=r) {
				int mid=(l+r)>>1;
				if(chk(mid)) x=mid,r=mid-1;
				else l=mid+1;
			}
			C.push_back(Ne[x]);
			Ne.erase(Ne.begin(),Ne.begin()+x+1);
		}
		for(int v:C) F.merge(u,v);
	}
	for(int i=0;i<n;++i) {
		int c=F.find(i);
		R[c].push_back(i);
		for(int j:G[i]) if(c!=F.find(j)) E[c].push_back(F.find(j));
	}
	vector <int> S[2];
	function<void(int,int,int)> dfs=[&](int u,int fz,int c) {
		S[c].push_back(u);
		for(int v:E[u]) if(v^fz) dfs(v,u,c^1);
	};
	dfs(F.find(0),-1,0);
	solve(S[0]),solve(S[1]);
	vector <int> cols(n);
	for(int i=0;i<n;++i) cols[i]=col[F.find(i)];
	return cols;
}