#include "sphinx.h"
#include<iostream>
#include<cstdio>
#include<vector>
#define N 250
using namespace std;
int n,srt,belong[N+1],tong[N+1],length,depth[N+1],fa[N+1],rt[N+1],lg[N+1],st[N+1],leng,A[N+1];
vector<int>E[N+1];
vector<int>p[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;
}
int query(int x)
{
	bool op=0;
	vector<int>v(n);
	for (int i=0;i<n;++i) v[i]=n;
	for (int i=0;i<=x;++i) v[i]=-1;
	for (int i=0;i<n;++i)
		if (v[i]==n)
			op=1;
	return perform_experiment(v)-op;
}
int query2(int x,int d)
{
	bool op=0;
	vector<int>v(n);
	for (int i=0;i<n;++i) v[i]=n;
	for (int i=0;i<=x;++i) v[i]=-1;
	v[d]=-1;
	for (int i=0;i<n;++i)
		if (v[i]==n)
			op=1;
	return perform_experiment(v)-op;
}
int query3(int x,int d)
{
	bool op=0;
	vector<int>v(n);
	for (int i=0;i<n;++i) v[i]=n;
	for (int i=2;i<=x;++i) v[tong[i]]=-1;
	v[srt]=d;
	for (int i=0;i<n;++i)
		if (v[i]==n)
			op=1;
	return perform_experiment(v)-op;
}
int get(int x)
{
	vector<int>v(n);
	for (int i=0;i<n;++i)
	{
		for (int j=0;j<n;++j) v[j]=(j==srt)?-1:i;
		if (perform_experiment(v)==1) return i;
	}
	return -1;
}
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;
	for (int i=0;i<n;++i) A[i]=query(i);
	for (int i=1;i<n;++i)
	{
		if (A[i]==A[i-1])
		{
			ps=-1;
			for (int j=lg[i];j>=0;--j)
				if (ps+(1<<j)<=i-2&&query2(ps+(1<<j),i)!=A[ps+(1<<j)])
					ps+=(1<<j);
			ps++,belong[i]=belong[ps],p[belong[i]].push_back(i);
		}
		else belong[i]=i,p[belong[i]].push_back(i);
	}
	for (int i=0;i<n;++i)
		if (belong[i]==i)
			tong[++length]=i;
	G[tong[1]]=get(tong[1]),srt=tong[1];
	if (length>=2)
	{
		for (int i=0;i<n;++i)
			if (query3(length,i)==length-1)
			{
				ps=1;
				for (int j=lg[length];j>=0;--j)
					if (ps+(1<<j)<=length&&query3(ps+(1<<j),i)!=ps+(1<<j)-1)
						ps+=(1<<j);
				ps++;
				for (int j=0;j<p[tong[ps]].size();++j) G[p[tong[ps]][j]]=i;
			}
	}
	for (int i=0;i<n;++i)
		if (belong[i]==i)
		{
			for (int j=0;j<p[i].size();++j) G[p[i][j]]=G[i];
		}
	return G;
}