#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

bool vis[256];
set<int> g[256];
vi S, T, f[256], c[256], res;
int fa[256], bel[256], n;

inline int findfa(int x) { return x == fa[x] ? x : fa[x] = findfa(fa[x]); }

void dfs(int u, bool c)
{
	vis[u] = 1;
	if (c) T.emplace_back(u), bel[u] = 1;
	else S.emplace_back(u), bel[u] = 0;
	for (auto v : g[u]) if (!vis[v]) dfs(v, !c);
}

vi e;
void col1(int u)
{
	e[u] = -1;
	for (int v : f[u]) col1(v);
}

void col2(int u, int c)
{
	res[u] = c;
	for (int v : f[u]) col2(v, c);
}

bool vs[256];
void ds(int u)
{
	vs[u] = 1;
	for (int v : c[u]) if (!vs[v] && ~e[v]) ds(v);
}

int cal()
{
	int cnt = 0;
	for (int i = 0; i < n; i++) vs[i] = 0;
	for (int i = 0; i < n; i++)
	{
		if (e[i] == -1) continue;
		if (!vs[i]) ds(i), cnt++;
	}
	return cnt;
}

bool exp1(vi nw, int u, int col)
{
	for (int i = 0; i < n; i++) e[i] = col;
	for (int v : nw) col1(v); if (~u) col1(u);
	return perform_experiment(e) != nw.size() + cal() + (u != -1);
}

void clr(vi &S, bool op)
{
	for (int i = 0; i < S.size(); i++)
	{
		int u = S[i];
		vi nw; nw.clear();
		for (auto v : g[u]) if (bel[v] == op) nw.emplace_back(v);
		if (!nw.size() || !exp1(nw, u, n)) continue;
		int l = 0, r = nw.size() - 1, pos = 0;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			vi tmp; tmp.clear();
			for (int j = l; j <= mid; j++) tmp.emplace_back(nw[j]);
			if (exp1(tmp, u, n)) pos = mid, r = mid - 1;
			else l = mid + 1;
		}
		int v = nw[pos]; f[v].emplace_back(u);
		for (auto x : g[u])
		{
			g[x].erase(u);
			if (x != v) g[v].insert(x), g[x].insert(v);
		}
		g[u].clear(); bel[u] = -1;
		for (int j = i + 1; j < S.size(); j++) S[j - 1] = S[j];
		S.pop_back(); i--;
	}
}

void fnd(vi S)
{
	for (int c = 0; c < n; c++)
	{
		while (S.size())
		{
			if (!exp1(S, -1, c)) break;
			int l = 0, r = S.size() - 1, pos = 0;
			while (l <= r)
			{
				vi tmp; tmp.clear();
				int mid = (l + r) >> 1;
				for (int i = l; i <= mid; i++) tmp.emplace_back(S[i]);
				if (exp1(tmp, -1, c)) pos = mid, r = mid - 1;
				else l = mid + 1;
			}
			col2(S[pos], c);
			for (int i = pos + 1; i < S.size(); i++) S[i - 1] = S[i]; S.pop_back();
		}
	}
}

vi find_colours(int N, vi X, vi Y)
{
	e.resize(N); res.resize(N);
	for (int i = 0; i < N; i++) g[i].clear(), f[i].clear(), c[i].clear(), vis[i] = 0; S.clear(), T.clear();
	for (int i = 0; i < X.size(); i++) g[X[i]].insert(Y[i]), g[Y[i]].insert(X[i]), c[X[i]].emplace_back(Y[i]), c[Y[i]].emplace_back(X[i]);
	dfs(0, 0); n = N; clr(S, 0), clr(T, 1); fnd(S), fnd(T); return res;
}