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

int n,CC;
vector<int> G[255],C;
// map<vector<int>,int> mp;
map<ull,int> mp;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
ull V[10011];
int Q(vector<int> E)
{
	// if(mp.find(E)!=mp.end())return mp[E];
	// ++CC;
	ull H=0;
	for(int i=0;i<n;++i)H+=V[i]*E[i];
	if(mp.find(H)!=mp.end())return mp[H];
	else return mp[H]=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];
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);
	// printf("res:%d cnt:%d\n",res,cnt);
	if(cnt==res)return 0;
	if(res==count_components(E))
	{
		for(int x=1;x<=n;++x)if(C[x]!=n)
		{
			for(int y:G[x])if(C[y]!=n&&get(y)!=get(x))
			{
				// printf("merge(%d,%d)\n",get(x),get(y));
				for(int z:vh[get(y)])vh[get(x)].push_back(z);
				fa[get(y)]=get(x);
				// printf("vh:\n");
				// for(int i=1;i<=n;++i)if(fa[i]==i)
				// {
				// 	printf("vh[%d]:",i);for(int x:vh[i])printf("%d ",x);putchar(10);
				// }
			}
		}
		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);
		// printf("S:");for(int x:S)printf("%d ",x);putchar(10);
		Sl=vector<int>(S.begin(),S.begin()+(S.size()+1)/2);
	}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)V[i]=rnd();
  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;
}