#include<bits/stdc++.h>
using namespace std;
#include "sphinx.h"
int n,m;
vector<int>C,G;
int fa[255],u[100005],v[100005];
int findfather(int x){
return x==fa[x]?x:fa[x]=findfather(fa[x]);
}
int aa[255];
int findaa(int x){
return x==aa[x]?x:aa[x]=findaa(aa[x]);
}
bool fff=0;int ct=0;
int qqq(std::vector<int> x) {
ct++;
if(ct>=2751) {
fff=1;
return 0;
}
int tx=perform_experiment(x);
return tx;
}
vector<int>gg[255];
int ss[255],vist[255],tt,I;
int query(int l,int r){
for(int i=0;i<n;++i)vist[i]=0,aa[i]=i,C[i]=n;
for(int i=l;i<=r;++i)for(auto cu:gg[ss[i]])vist[cu]=1,C[cu]=-1;
vist[I]=1,C[I]=-1;
for(int i=0;i<m;++i)if(!vist[u[i]]&&!vist[v[i]]){
int fu=findaa(u[i]),fv=findaa(v[i]);
if(fu!=fv)aa[fu]=fv;
}
int cnt=0;
for(int i=0;i<n;++i)if(!vist[i]&&aa[i]==i)++cnt;
return r-l+1+1+cnt-qqq(C);
}
double ef=0.37;
void solve(int l,int r,int k){
if(!k)return;
if(l==r){
fa[ss[l]]=I;
return;
}
int mid=(l+r)>>1;
mid=min(r+0.0,l+ef*(r-l));
int k1=query(l,mid);
solve(l,mid,k1);
solve(mid+1,r,k-k1);
}
int s1[255],s2[255];
vector<int>g[255];
int dep[255];
void dfs(int x){
vist[x]=1;
for(auto cu:g[x])if(!vist[cu]){
dep[cu]=dep[x]+1;
dfs(cu);
}
}
int p[255],v1[255],v2[255],ss1[255],ss2[255];
int query1(int l,int r,int d){
for(int i=0;i<n;++i)vist[i]=0,aa[i]=i,C[i]=d;
for(int i=l;i<=r;++i)for(auto cu:gg[ss1[i]])vist[cu]=1,C[cu]=-1;
for(int i=0;i<m;++i)if(!vist[u[i]]&&!vist[v[i]]){
int fu=findaa(u[i]),fv=findaa(v[i]);
if(fu!=fv)aa[fu]=fv;
}
int cnt=0;
for(int i=0;i<n;++i)if(!vist[i]&&aa[i]==i)++cnt;
return r-l+1+cnt-qqq(C);
}
int query2(int l,int r,int d){
for(int i=0;i<n;++i)vist[i]=0,aa[i]=i,C[i]=d;
for(int i=l;i<=r;++i)for(auto cu:gg[ss2[i]])vist[cu]=1,C[cu]=-1;
for(int i=0;i<m;++i)if(!vist[u[i]]&&!vist[v[i]]){
int fu=findaa(u[i]),fv=findaa(v[i]);
if(fu!=fv)aa[fu]=fv;
}
int cnt=0;
for(int i=0;i<n;++i)if(!vist[i]&&aa[i]==i)++cnt;
return r-l+1+cnt-qqq(C);
}
void solve1(int l,int r,int d){
if(l==r){
G[ss1[l]]=d;v1[ss1[l]]=1;
return;
}
int mid=min(r+0.0,l+(r-l)*ef);
int f1=query1(l,mid,d);
if(!f1){
solve1(mid+1,r,d);
}else{
solve1(l,mid,d);
if(query1(mid+1,r,d))solve1(mid+1,r,d);
}
}
void solve2(int l,int r,int d){
if(l==r){
G[ss2[l]]=d;v2[ss2[l]]=1;
return;
}
int mid=min(r+0.0,l+(r-l)*ef);
int f1=query2(l,mid,d);
if(!f1){
solve2(mid+1,r,d);
}else{
solve2(l,mid,d);
if(query2(mid+1,r,d))solve2(mid+1,r,d);
}
}
vector<int>find_colours(int N,vector<int>X,vector<int>Y){
n=N;m=X.size();
C.resize(n);G.resize(n);
for(int i=0;i<m;++i){
u[i]=X[i],v[i]=Y[i];
}
for(int i=0;i<n;++i)fa[i]=i;
for(int i=0;i<n;++i)p[i]=i;
mt19937 mt(1233);
if(M<N*(N-1)/2) {
shuffle(p,p+n,mt);
for(int x=1;x<n;++x){
int i=p[x];
I=i;
for(int j=0;j<x;++j)gg[p[j]].clear();
for(int j=0;j<x;++j){
gg[findfather(p[j])].emplace_back(p[j]);
}
tt=0;
for(int j=0;j<x;++j)if(gg[p[j]].size())ss[++tt]=p[j];
solve(1,tt,query(1,tt));
}
}
for(int j=0;j<n;++j)gg[j].clear();
for(int j=0;j<n;++j){
gg[findfather(j)].emplace_back(j);
}
for(int i=0;i<n;++i)g[i].clear();
for(int i=0;i<m;++i)if(findfather(u[i])!=findfather(v[i])){
int fu=fa[u[i]],fv=fa[v[i]];
g[fu].emplace_back(fv);
g[fv].emplace_back(fu);
}
int r=findfather(0);
for(int i=0;i<n;++i)vist[i]=0;
dep[r]=0;dfs(r);
int t1=0,t2=0;
for(int i=0;i<n;++i)if(fa[i]==i){
if(dep[i]%2)s1[++t1]=i;
else s2[++t2]=i;
}
if(t1+t2==1){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)G[j]=(j==0?-1:i);
if(qqq(G)==1){
for(int j=0;j<n;++j)G[j]=i;
break;
}
}
return G;
}
for(int i=0;i<n;++i)v1[i]=v2[i]=0;
for(int i=0;i<n;++i)p[i]=i;
shuffle(p,p+n,mt);
for(int dd=0;dd<n;++dd){
int d=p[dd];
int tt1=0,tt2=0;
for(int i=1;i<=t1;++i)if(!v1[s1[i]]){
ss1[++tt1]=s1[i];
}
for(int i=1;i<=t2;++i)if(!v2[s2[i]]){
ss2[++tt2]=s2[i];
}
shuffle(ss1+1,ss1+tt1+1,mt);
shuffle(ss2+1,ss2+tt2+1,mt);
if(tt1&&query1(1,tt1,d))solve1(1,tt1,d);
if(tt2&&query2(1,tt2,d))solve2(1,tt2,d);
}
if(fff) for(int i=0;i<n;i++) G[i]=fa[i];
else for(int i=0;i<n;++i)G[i]=G[fa[i]];
return G;
}