#include<bits/stdc++.h>
#define MAXN 307
#include "sphinx.h"
using namespace std;
int n,m;
int color[MAXN];
int li[MAXN],tim;
vector<int> v[MAXN];
int query(){
vector<int> w;
for(int i=1;i<=n;i++){
w.push_back(color[i]);
}
return perform_experiment(w);
}
struct union_find{
int dsu[MAXN];
void init(){
for(int i=1;i<=n;i++)dsu[i]=i;
}
int root(int x){
if(dsu[x]==x)return x;
dsu[x]=root(dsu[x]);
return dsu[x];
}
void mergev(int x,int y){
int rootx=root(x);
int rooty=root(y);
dsu[rootx]=rooty;
}
}graph;
void dfs(int x){
li[x]=tim;
for(int i:v[x]){
if(li[i]==tim)continue;
if((color[i]==n and color[x]==n) or (graph.root(i)==graph.root(x) and color[i]==-1 and color[x]==-1)){
dfs(i);
}
}
}
int calc_comps(){
tim++;
int c=0;
for(int i=1;i<=n;i++){
if(li[i]==tim)continue;
c++;
dfs(i);
}
return c;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
n=N; m=int(X.size());
for(int i=0;i<m;i++){
X[i]++; Y[i]++;
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
for(int i=1;i<=n;i++)color[i]=n;
graph.init();
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++)color[f]=n;
color[i]=-1;
tim++;
vector<int> s;
for(int f:v[i]){
if(f>i)continue;
if(li[graph.root(f)]!=tim){
color[f]=-1;
s.push_back(f);
}
li[graph.root(f)]=tim;
}
while(!s.empty()){
if(calc_comps()==query())break;
int l=0,r=s.size(),tt;
while(l+1<r){
tt=(l+r)/2;
for(int i=0;i<tt;i++)color[s[i]]=n;
if(calc_comps()==query()){
r=tt;
}else{
l=tt;
}
for(int i=0;i<tt;i++)color[s[i]]=-1;
}
graph.mergev(i,s[l]);
while(int(s.size())>l){
color[s.back()]=n;
s.pop_back();
}
}
}
vector<int> sol;
for(int i=1;i<=n;i++){
sol.push_back(graph.root(i)-1);
}
return sol;
}
