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

using namespace std;

//perform_experiment
const int N = 255;
int col[N];
bool vis[N];
vector<int> e[N], T[2], tmp, res, owo;
int fa[N], tp[N], cnt[N], awa[N], cry[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> G)
{
	int n, i;
	vector<int> tmp;
	n = G.size();
	for(i = 0; i < n; i++)
		if(G[i] == n)
			tmp.emplace_back(i);
	return num(n, tmp);
}
void dfs(int x, int c)
{
	col[x] = c;
	vis[x] = 1;
	for(auto y: e[x])
		if(!vis[y])
			dfs(y, 1 ^ c);
}
vector<int> find_colours(int n, vector<int> X, vector<int> Y)
{
	vector<int> E(n, -1);
	vector<int> G(n, 0);
	int i, j, k, m = X.size(), x, y, l, r, mid, C = 0;
	for(i = 0; i < m; i++)
	{
		e[X[i]].emplace_back(Y[i]);
		e[Y[i]].emplace_back(X[i]);
	}
	dfs(1, 0);
	for(i = 0; i < n; i++)
		T[col[i]].emplace_back(i);
	for(i = 0; i < 2; i++)
	{
		x = num(n, T[i ^ 1]);
		res = T[i];
		for(j = 0; j < n; j++)
			tp[j] = 0;
		for(auto o: T[i])
			tp[o] = 1;
		for(j = 0; j < n; j++)
			G[j] = n;
		y = 0;
		for(j = 0; j < n; j++)
		{
			if(tp[j])
			{
				G[j] = -1;
				cnt[j] = perform_experiment(G) - qwq(G);
				++C;
			}
			else
				cnt[j] = (j ? cnt[j - 1] : 0);
		}
		tmp.clear();
		// for(auto o: T[i])
		// 	cerr << "!" << i << " " << o << " " << cnt[o] << " " << x << endl;
		for(j = 0; j < n; j++)
			awa[j] = 0;
		for(j = 0; j < n; j++)
		{
			if(res.empty())
				break;
			for(k = 0; k < n; k++)
				G[k] = n;
			for(auto o: res)
				G[o] = -1;
			for(auto o: T[i ^ 1])
				G[o] = j;
			y = perform_experiment(G) - qwq(G) - x - cnt[res.back()];
			++C;
			// cerr << "WOW" << j << " " << y << " " << res.size() << " " << qwq(G) << " " << x << " " << res.back() << " " << cnt[res.back()] << endl;
			if(y == 0)
			{
				tmp.clear();
				for(k = 0; k < n; k++)
					awa[k] = 0;
				continue;
			}
			l = 0;
			r = res.size() - 1;
			while(l <= r)
			{
				mid = (l + r) >> 1;
				for(k = 0; k < n; k++)
					G[k] = n;
				for(k = 0; k <= mid; k++)
					G[k] = -1;
				for(auto o: T[i ^ 1])
					G[o] = j;
				y = perform_experiment(G) - qwq(G) - x - cnt[res[mid]];
				++C;
				if(y == 0)
					l = mid + 1;
				else
					r = mid - 1;
			}
			E[res[l]] = j;
			tmp.emplace_back(res[l]);
			owo.clear();
			for(auto o: res)
				if(o != res[l])
					owo.emplace_back(o);
			res = owo;
			owo.clear();
			for(k = 0; k < n; k++)
				cry[k] = 0;
			for(auto o: tmp)
				cry[o] = 1;
			y = 0;
			for(k = 0; k < n; k++)
			{
				if(cry[k])
				{
					owo.emplace_back(k);
					y = num(n, owo);
				}
				if(y != awa[k])
				{
					cnt[k] += awa[k] - y;
					awa[k] = y;
				}
			}
			j--;
		}
	}
	assert(C <= 2200);
	return E;
}