#include "sphinx.h"
#include<iostream>
#include<cstdio>
#include<vector>
#define N 250
using namespace std;
int n,srt,wcnt,depth[N+1],fa[N+1],rt[N+1],tong[N+1],tong2[N+1],length,length2,lg[N+1],st[N+1],leng,A[N+1],B[N+1],D[N+1],F[N+1];
vector<int>E[N+1];
bool used[N+1],vis[N+1];
int find(int x)
{
	if (rt[x]==x) return x;
	return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
	rt[x]=y;
	return;
}
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	if (!(depth[x]&1)) tong[++length]=x;
	else tong2[++length2]=x;
	used[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
			fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,dfs(E[x][i]);
	return;
}
int calc(int x,int type)
{
	vector<int>v(n);
	for (int i=0;i<n;++i) v[i]=n;
	for (int i=0;i<n;++i) vis[i]=0;
	if (!type)
	{
		for (int i=1;i<=x;++i) v[tong[i]]=-1;
	}
	else
	{
		for (int i=1;i<=x;++i) v[tong2[i]]=-1;
	}
	int d=perform_experiment(v),cnt=0;
	for (int i=0;i<n;++i)
		if (v[i]==n)
			rt[i]=i,cnt++;
	for (int i=0;i<n;++i)
		if (v[i]==n)
		{
			for (int j=0;j<E[i].size();++j)
				if (v[E[i][j]]==n&&find(i)!=find(E[i][j]))
					unionn(find(i),find(E[i][j])),cnt--;
		}
	return d-cnt;
}
int calc2(int x,int type)
{
	vector<int>v(n);
	for (int i=0;i<n;++i) v[i]=n;
	for (int i=0;i<n;++i) vis[i]=0;
	if (!type)
	{
		for (int i=x;i<=length;++i) v[tong[i]]=-1;
	}
	else
	{
		for (int i=x;i<=length2;++i) v[tong2[i]]=-1;
	}
	int d=perform_experiment(v),cnt=0;
	for (int i=0;i<n;++i)
		if (v[i]==n)
			rt[i]=i,cnt++;
	for (int i=0;i<n;++i)
		if (v[i]==n)
		{
			for (int j=0;j<E[i].size();++j)
				if (v[E[i][j]]==n&&find(i)!=find(E[i][j]))
					unionn(find(i),find(E[i][j])),cnt--;
		}
	return d-cnt;
}
int solve(int x,int type)
{
	int d,cnt=0;
	if (!type) d=A[x];
	else d=B[x];
	for (int i=0;i<n;++i) vis[i]=0;
	for (int i=1;i<=leng;++i) vis[st[i]]=1;
	for (int i=0;i<n;++i)
		if (vis[i])
			rt[i]=i,cnt++;
	for (int i=0;i<n;++i)
		if (vis[i])
		{
			for (int j=0;j<E[i].size();++j)
				if (vis[E[i][j]]&&find(i)!=find(E[i][j]))
					unionn(find(i),find(E[i][j])),cnt--;
		}
	return d-wcnt;
}
int get(int x,int type)
{
	vector<int>v(n);
	for (int i=0;i<n;++i) v[i]=n;
	for (int i=0;i<n;++i) vis[i]=0;
	if (!type)
	{
		for (int i=1;i<=x;++i)
		{
			v[tong[i]]=-1;
			for (int j=0;j<E[tong[i]].size();++j)
				if (fa[E[tong[i]][j]]==tong[i]||fa[tong[i]]==E[tong[i]][j])
					vis[E[tong[i]][j]]=1;
		}
	}
	else
	{
		for (int i=1;i<=x;++i)
		{
			v[tong2[i]]=-1;
			for (int j=0;j<E[tong2[i]].size();++j)
				if (fa[E[tong2[i]][j]]==tong2[i]||fa[tong2[i]]==E[tong2[i]][j])
					vis[E[tong2[i]][j]]=1;
		}
	}
	for (int i=1;i<=leng;++i) v[st[i]]=n;
	for (int i=0;i<n;++i)
		if (vis[i])
			v[i]=srt;
	int d=perform_experiment(v),cnt=0;
	for (int i=0;i<n;++i)
		if (v[i]==srt||v[i]==n)
			rt[i]=i,cnt++;
	for (int i=0;i<n;++i)
		if (v[i]==srt||v[i]==n)
		{
			for (int j=0;j<E[i].size();++j)
				if (v[E[i][j]]==v[i]&&find(i)!=find(E[i][j]))
					unionn(find(i),find(E[i][j])),cnt--;
		}
	return d-cnt;
}
std::vector<int> find_colours(int SN, std::vector<int> X, std::vector<int> Y) {
	vector<int>G(SN);
	int ps;
	n=SN;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	for (int i=0;i<X.size();++i) add(X[i],Y[i]);
	fa[0]=-1,dfs(0);
	for (int i=1;i<=length;++i) A[i]=calc(i,0),D[i]=calc2(i,0);
	for (int i=1;i<=length2;++i) B[i]=calc(i,1),F[i]=calc2(i,1);
	for (int i=0;i<n;++i)
	{
		srt=i,ps=leng=wcnt=0;
		while (ps<=length&&get(length,0)!=solve(length,0))
		{
			for (int j=lg[length];j>=0;--j)
				if (ps+(1<<j)<=length&&get(ps+(1<<j),0)==solve(ps+(1<<j),0))
					ps+=(1<<j);
			ps++;
			if (ps<=length)
			{
				st[++leng]=tong[ps],wcnt=D[ps]!=D[ps+1],G[tong[ps]]=i;
				if (wcnt) break;
			}
		}
	}
	for (int i=0;i<n;++i)
	{
		srt=i,ps=leng=wcnt=0;
		while (ps<=length2&&get(length,1)!=solve(length,1))
		{
			for (int j=lg[length2];j>=0;--j)
				if (ps+(1<<j)<=length2&&get(ps+(1<<j),1)==solve(ps+(1<<j),1))
					ps+=(1<<j);
			ps++;
			if (ps<=length2)
			{
				st[++leng]=tong2[ps],wcnt=F[ps]!=F[ps+1],G[tong2[ps]]=i;
				if (wcnt) break;
			}
		}
	}
	return G;
}