#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
const int NR=300;
int n,m,c[NR],fa[NR],tot,cnt,opt[NR],ans[NR],nc[NR];
vector<int>g[NR];
#define pb emplace_back
void init(){
for(int i=1;i<=n;i++)fa[i]=i;
cnt=n;
}
int get(int x){
if(fa[x]==x)return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y){
x=get(x);y=get(y);
if(x==y)return;
fa[x]=y;cnt--;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
n=N;m=X.size();
for(int i=0;i<m;i++)g[X[i]+1].pb(Y[i]+1),g[Y[i]+1].pb(X[i]+1);
for(int i=1;i<=n;i++)c[i]=i-1;
for(int i=1;i<=n;i++){
vector<int>buc;
for(int x:g[i])
if(x<i)buc.pb(x);
if(!buc.size())continue;
sort(buc.begin(),buc.end());
// printf("i:%d\n",i);
// for(int x:buc)printf("%d ",x);puts("");
int L=0,R=buc.size()-1;
while(L<=R){
init();
for(int j=1;j<=n;j++)opt[j]=-1;
for(int j=L;j<=R;j++)opt[buc[j]]=1;
opt[i]=1;
for(int j=1;j<=n;j++)
for(int x:g[j])
if(opt[j]==opt[x]){
if(opt[j]==-1)merge(j,x);
else if(c[j]==c[x])merge(j,x);
}
// printf("mid:%d cnt:%d\n",mid,cnt);
// for(int j=1;j<=n;j++)printf("%d ",opt[j]);puts("");
// for(int j=1;j<=n;j++)printf("%d ",get(j));puts("");
vector<int>arr;
for(int i=1;i<=n;i++)
if(opt[i]==-1)arr.pb(n);
else arr.pb(-1);
int tmp=perform_experiment(arr);
if(tmp==cnt)break;
int l=L,r=R,res=-1;
while(l<=r){
int mid=(l+r)>>1;init();
for(int j=1;j<=n;j++)opt[j]=-1;
for(int j=L;j<=mid;j++)opt[buc[j]]=1;
opt[i]=1;
for(int j=1;j<=n;j++)
for(int x:g[j])
if(opt[j]==opt[x]){
if(opt[j]==-1)merge(j,x);
else if(c[j]==c[x])merge(j,x);
}
// printf("mid:%d cnt:%d\n",mid,cnt);
// for(int j=1;j<=n;j++)printf("%d ",opt[j]);puts("");
// for(int j=1;j<=n;j++)printf("%d ",get(j));puts("");
vector<int>arr;
for(int i=1;i<=n;i++)
if(opt[i]==-1)arr.pb(n);
else arr.pb(-1);
int tmp=perform_experiment(arr);
// printf("tmp:%d\n",tmp);
if(tmp!=cnt)res=mid,r=mid-1;
else l=mid+1;
}
if(res==-1)break;
else{
int x=c[buc[res]];
for(int j=1;j<=n;j++)
if(c[j]==x)c[j]=i-1;
L=res+1;
}
}
}
bool ok=1;
for(int i=1;i<=n;i++)ok&=(c[i]==n-1);
if(ok){
int ans=0;
for(int c=0;c<n;c++){
init();
for(int j=1;j<n;j++)opt[j]=-1;opt[n]=1;
for(int j=1;j<=n;j++)
for(int x:g[j])
if(opt[j]==-1&&opt[x]==-1)merge(j,x);
vector<int>arr;
for(int i=1;i<=n;i++)
if(opt[i]==1)arr.pb(-1);
else arr.pb(c);
int tmp=perform_experiment(arr);
// printf("c:%lld cnt:%lld tmp:%lld\n",c,cnt,tmp);
if(tmp!=cnt){
ans=c;
break;
}
}
vector<int>arr;
for(int i=1;i<=n;i++)arr.pb(ans);
return arr;
}
for(int i=1;i<=n;i++)
if(c[i]==i-1){
vector<int>buc;
for(int j=1;j<=n;j++)
if(c[i]==c[j])buc.pb(j);
set<int>s;
for(int x:buc)
for(int y:g[x])
if(c[y]!=c[i])s.insert(y);
int k=s.size(),now=0,res=-1,l,r;
// printf("i:%d\n",i);
while(now<n-1){
for(int j=1;j<=n;j++)opt[j]=-1;
for(int x:buc)opt[x]=1;
for(int x:s)opt[x]=0;
init();
int now=l;
for(int i=1;i<=n;i++)
if(!opt[i])nc[i]=min(now++,mid);
for(int j=1;j<=n;j++)
for(int x:g[j])
if(opt[j]==opt[x]){
if(opt[j]==-1)merge(j,x);
else if(opt[j]==1)merge(j,x);
else if(opt[j]==0&&nc[j]==nc[x])merge(j,x);
}
vector<int>arr;
for(int i=1;i<=n;i++)
if(!opt[i])arr.pb(nc[i]);
else if(opt[i]==-1)arr.pb(n);
else arr.pb(-1);
int tmp=perform_experiment(arr);
// printf("now:%d k:%d %d %d\n",now,k,cnt,tmp);
if(tmp!=cnt){
r=min(now-1,n-2);l=now-k;res=0;
break;
}
}
if(res==-1)ans[i]=n-1;
else{
while(l<r){
int mid=(l+r)>>1;
for(int j=1;j<=n;j++)opt[j]=-1;
for(int x:buc)opt[x]=1;
for(int x:s)opt[x]=0;
init();
int now=l;
for(int i=1;i<=n;i++)
if(!opt[i])nc[i]=min(now++,mid);
for(int j=1;j<=n;j++)
for(int x:g[j])
if(opt[j]==opt[x]){
if(opt[j]==-1)merge(j,x);
else if(opt[j]==1)merge(j,x);
else if(opt[j]==0&&nc[j]==nc[x])merge(j,x);
}
vector<int>arr;
for(int i=1;i<=n;i++)
if(!opt[i])arr.pb(nc[i]);
else if(opt[i]==-1)arr.pb(n);
else arr.pb(-1);
int tmp=perform_experiment(arr);
if(tmp!=cnt)r=mid;
else l=mid+1;
}
ans[i]=l;
}
}
vector<int>arr;
for(int i=1;i<=n;i++)arr.pb(ans[c[i]+1]);
return arr;
}