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

int n,CC;
vector<int> G[255],C;
// map<vector<int>,int> mp;
int Q(vector<int> E)
{
	// if(mp.find(E)!=mp.end())return mp[E];
	// ++CC;
	return perform_experiment(E);
}
int count_components(const std::vector<int>& S) {
  int components_cnt = 0;
  std::vector<bool> vis(n, false);
  for (int i = 0; i < n; i++) {
    if (vis[i])
      continue;
    components_cnt++;

    std::queue<int> q;
    vis[i] = true;
    q.push(i);
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int nxt : G[cur])
        if (!vis[nxt] && S[nxt] == S[cur]) {
          vis[nxt] = true;
          q.push(nxt);
        }
    }
  }
  return components_cnt;
}
int fa[255];
int get(int a){return fa[a]==a?a:fa[a]=get(fa[a]);}
vector<int> vh[255];
mt19937 rnd(801);
bool solve(vector<int> S)
{
	if(S.size()<=1)return 0;
	// printf("solve(S:");for(int x:S)printf("%d ",x);printf(")\n");
	vector<int> Sl;
	vector<int> E(n,n),C(n,n);
	for(int x:S)
	{
		for(int y:vh[x])C[y]=-x,E[y]=-1;
	}
	int res=Q(E);
	int cnt=count_components(C);
	if(cnt==res)return 0;
	if(res==count_components(E))
	{
		for(int i=1;i<S.size();++i)
		{
			fa[S[i]]=S[0];
			for(int x:vh[S[i]])vh[S[0]].push_back(x);
		}
		return 1;
	}
	// if(S.size()==2)
	// {
	// 	printf("merge(%d,%d) CNT:%d\n",S[0],S[1],CC);
	// 	fa[S[1]]=S[0];
	// 	for(int x:vh[S[1]])vh[S[0]].push_back(x);
	// 	return 1;
	// }
	do
	{
		shuffle(S.begin(),S.end(),rnd);
		Sl=vector<int>(S.begin(),S.begin()+S.size()/2+1);
	}while(!solve(Sl));
	return 1;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
  n=N;
  for(int i=0;i<X.size();++i)G[X[i]].push_back(Y[i]),G[Y[i]].push_back(X[i]);
  for(int i=0;i<n;++i)fa[i]=i,vh[i].push_back(i);
  vector<int> all(n,0);
  C.resize(n,n);
  for(int i=0;i<n;++i)all[i]=i;
  while(solve(all))
  {
	vector<int> nall;
	for(int x:all)if(fa[x]==x)nall.push_back(x);
	all=nall;
  }
  for(int i=0;i<n;++i)if(fa[i]==i)for(int v:vh[i])C[v]=i;
  return C;
}