#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

//perform_experiment
const int N = 255;
vector<int> e[N], se[N];
int fa[N];
int getf(int x)
{
	return (fa[x] == x) ? x : (fa[x] = getf(fa[x]));
}
void un(int x, int y)
{
	fa[getf(x)] = getf(y);
}
int num(int n, vector<int> p)
{
	int i, c = 0;
	for(i = 0; i < n; i++)
		fa[i] = -1;
	for(auto o: p)
		fa[o] = o;
	for(auto u: p)
		for(auto v: e[u])
			if(fa[v] != -1)
				un(u, v);
	for(auto o: p)
		if(fa[o] == o)
			++c;
	return c;
}
int qwq(vector<int> E)
{
	int n, i;
	vector<int> tmp;
	n = E.size();
	for(i = 0; i < n; i++)
		if(E[i] == n)
			tmp.emplace_back(i);
	return num(n, tmp);
}
int col[N];
bool vis[N];
void dfs(int x, int c)
{
	col[x] = c;
	vis[x] = 1;
	for(auto y: se[x])
		if(!vis[y])
			dfs(y, 1 ^ c);
}

int anc[N], tp[N], nmm[N];
vector<int> tmp, T[2], res, ch[N];
vector<int> find_colours(int n, vector<int> X, vector<int> Y)
{
	vector<int> E(n, -1);
	vector<int> G(n, -1);
	int i, j, t, m = X.size(), x, y, l, r, mid;
	for(i = 0; i < m; i++)
	{
		e[X[i]].emplace_back(Y[i]);
		e[Y[i]].emplace_back(X[i]);
	}
	for(i = 0; i < n; i++)
		anc[i] = i;
	tmp.emplace_back(0);
	nmm[0] = 1;
	for(i = 1; i < n; i++)
	{
		for(j = 0; j <= i; j++)
			E[j] = -1;
		for(j = i + 1; j < n; j++)
			E[j] = n;
		nmm[i] = perform_experiment(E) - qwq(E);
	}
	for(i = 0; i < n; i++)
	{
		if(nmm[i] == tmp.size() + 1)
		{
			tmp.emplace_back(i);
			continue;
		}
		x = tmp.size() + 1 - nmm[i];
		// cerr << "!!" << i << " " << x << endl;
		while(x--)
		{
			l = 0;
			r = tmp.size() - 1;
			while(l <= r)
			{
				mid = (l + r) >> 1;
				for(j = 0; j < n; j++)
					tp[j] = 0;
				for(j = 0; j <= mid; j++)
					tp[tmp[j]] = 1;
				tp[i] = 1;
				for(j = 0; j < n; j++)
					E[j] = (tp[anc[j]] ? -1 : n);
				y = perform_experiment(E) - qwq(E);
				if(y != mid + 2)
					r = mid - 1;
				else
					l = mid + 1;
			}
			for(j = 0; j < n; j++)
				if(anc[j] == tmp[l])
					anc[j] = i;
			tmp.erase(tmp.begin() + l);
		}
		tmp.emplace_back(i);
	}
	for(i = 0; i < n; i++)
		ch[anc[i]].emplace_back(i);
	for(i = 0; i < m; i++)
	{
		se[anc[X[i]]].emplace_back(anc[Y[i]]);
		se[anc[Y[i]]].emplace_back(anc[X[i]]);
	}
	dfs(anc[0], 0);
	for(i = 0; i < n; i++)
		if(anc[i] == i)
			T[col[i]].emplace_back(i);
	// cerr << "!!" << endl;
	for(t = 0; t < 2; t++)
	{
		res = T[t];
		// cerr << "TT" << t << endl;
		for(i = 0; i < n; i++)
		{
			if(res.empty())
				break;
			tmp.clear();
			for(j = 0; j < n; j++)
				E[j] = i;
			for(auto o: res)
				for(auto x: ch[o])
					E[x] = -1;
			for(j = 0; j < n; j++)
				if(E[j] == i)
					tmp.emplace_back(j);
			x = perform_experiment(E);
			y = num(n, tmp) + res.size() - x;
			// cerr << "FF" << i << " " << x << " " << y << endl;
			while(y)
			{
				l = 0;
				r = res.size() - 1;
				while(l <= r)
				{
					mid = (l + r) >> 1;
					for(j = 0; j < n; j++)
						E[j] = i;
					for(j = 0; j <= mid; j++)
						for(auto x: ch[res[j]])
							E[x] = -1;
					tmp.clear();
					for(j = 0; j < n; j++)
						if(E[j] == i)
							tmp.emplace_back(j);
					if(perform_experiment(E) != num(n, tmp) + mid + 1)
						r = mid - 1;
					else
						l = mid + 1;
				}
				for(auto o: ch[res[l]])
					G[o] = i;
				res.erase(res.begin() + l);
				for(j = 0; j < n; j++)
					E[j] = i;
				for(auto o: res)
					for(auto x: ch[o])
						E[x] = -1;
				tmp.clear();
				for(j = 0; j < n; j++)
					if(E[j] == i)
						tmp.emplace_back(j);
				y = num(n, tmp) + res.size() - x;
			}
		}
	}
	return G;
}