#include<bits/stdc++.h>
#define MAXN 307
#include "sphinx.h"
using namespace std;
int n,m,root;
int color[MAXN];
int li[MAXN],tim,ans[MAXN];
vector<int> v[MAXN],g[MAXN],comp[MAXN];
vector<int> seq[2];
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]>=0 and color[x]>=0 and color[i]==color[x]) 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;
}
void find_components(){
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();
}
}
}
for(int i=1;i<=n;i++){
comp[graph.root(i)].push_back(i);
}
}
void dfs2(int x,int side){
li[x]=tim;
seq[side].push_back(x);
for(int i:g[x]){
if(li[i]==tim)continue;
dfs2(i,side^1);
}
}
void fillc(int k,int c){
for(int i:comp[k])color[i]=c;
}
void find_colors(int id){
for(int curr=0;curr<n;curr++){
for(int i:seq[id])fillc(i,-1);
for(int i:seq[id^1])fillc(i,curr);
vector<int> s=seq[id];
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++)fillc(s[i],n);
if(calc_comps()==query()){
r=tt;
}else{
l=tt;
}
for(int i=0;i<tt;i++)fillc(s[i],-1);
}
ans[s[l]]=curr;
while(int(s.size())>l){
fillc(s.back(),n);
s.pop_back();
}
}
}
}
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]);
}
find_components();
for(int i=0;i<m;i++){
int a=graph.root(X[i]);
int b=graph.root(Y[i]);
if(a==b)continue;
g[a].push_back(b);
g[b].push_back(a);
root=a;
}
tim++;
dfs2(root,0);
vector<int> sol;
if(seq[0].empty() or seq[1].empty()){
for(int i=1;i<=n;i++)color[i]=-1;
for(int curr=0;curr<n;curr++){
color[1]=curr;
if(query()==1){
for(int f=1;f<=n;f++)sol.push_back(curr);
return sol;
}
}
}
find_colors(0);
find_colors(1);
for(int i=1;i<=n;i++){
sol.push_back(ans[graph.root(i)]);
}
return sol;
}
