#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 252
int n;
int cvet[MAXN];
vector<int> v[MAXN];
bool b[MAXN];
vector<vector<int>> komp;
bool c2[MAXN];
void dfs2(int x)
{
c2[x]=1;
for (int q=0;q<v[x].size();q++)
{
if (c2[v[x][q]]) continue;
if (cvet[ v[x][q] ]==-1) continue;
dfs2(v[x][q]);
}
}
bool check(int lf, int rt, int x)
{
int ans=rt-lf+2;
for (int q=0;q<n;q++) cvet[q]=n;
cvet[x]=-1;
for (int q=lf;q<=rt;q++)
{
for (int w=0;w<komp[q].size();w++) cvet[ komp[q][w] ]=-1;
}
vector<int> E(n,n);
E[x]=-1;
for (int q=lf;q<=rt;q++)
{
for (int w=0;w<komp[q].size();w++) E[ komp[q][w] ]=-1;
}
for (int q=0;q<n;q++) c2[q]=0;
for (int q=0;q<n;q++)
{
if (c2[q]) continue;
if (cvet[q]==-1) continue;
ans++;
dfs2(q);
}
int klk=perform_experiment(E);
if (klk<ans) return true;
return false;
}
void dfs(int x)
{
b[x]=1;
vector<int> moiko;
int lft=0;
while (true)
{
if (lft>=komp.size()) break;
bool ch=check(lft,komp.size()-1,x);
if (!ch) break;
int l=lft-1,r=komp.size()-1;
while (l<r-1)
{
int mid=(l+r)/2;
ch=check(lft,mid,x);
if (ch) r=mid;
else l=mid;
}
moiko.push_back(r);
lft=r+1;
}
if (moiko.size()==0)
{
vector<int> vvv(1,x);
komp.push_back(vvv);
}
else if (moiko.size()==1)
{
komp[ moiko[0] ].push_back(x);
}
else
{
komp[ moiko[0] ].push_back(x);
for (int q=moiko.size()-1;q>0;q--)
{
for (int w=0;w<komp[ moiko[q] ].size();w++) komp[ moiko[0] ].push_back(komp[ moiko[q] ][w]);
swap(komp[ moiko[q] ],komp[ komp.size()-1 ]);
komp.pop_back();
}
}
for (int q=0;q<v[x].size();q++)
{
if (b[v[x][q]]) continue;
dfs(v[x][q]);
}
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
vector<int> G(N, -1);
n=N;
for (int q=0;q<X.size();q++)
{
v[X[q]].push_back(Y[q]);
v[Y[q]].push_back(X[q]);
}
dfs(1);
for (int q=0;q<komp.size();q++)
{
for (int w=0;w<komp[q].size();w++) G[komp[q][w]]=q;
}
return G;
}
