#include "sphinx.h"

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=250+5,M=(1<<28)+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m;
vector<int> S[N];
int fa[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
int vis[N];
void dfs(int x,int c,vector<int> &E){
	if(vis[x]) return;
	vis[x]=1;
	for(int i:S[x]) if(E[i-1]==c) dfs(i,c,E);
}
int qry(vector<int> E){
	int w=perform_experiment(E);
	fill(vis+1,vis+n+1,0);
	for(int i=1;i<=n;i++) if(E[i-1]==n&&!vis[i]) dfs(i,n,E),w--;
	return w;
}
void find_merge(vector<int> pos,int p,int w){
	if(!w) return;
	if(pos.size()==1){
		fa[GF(pos[0])]=p;
		return;
	}
	vector<int> E(n,n);
	E[p-1]=-1;
	int len=pos.size()/2;
	vector<int> p1(pos.begin(),pos.begin()+len),p2(pos.begin()+len,pos.end());
	for(int i:p1) E[i-1]=-1;
	int sw=p1.size()+1-qry(E);
	find_merge(p1,p,sw);find_merge(p2,p,w-sw);
}
vector<int> G[N];
int op[N],col[N],id[N];
int find(vector<int> pos,vector<int> ps,int c,int cts){
	if(pos.size()==1) return pos[0];
	int len=pos.size()/2;
	vector<int> p1(pos.begin(),pos.begin()+len),p2(pos.begin()+len,pos.end());
	vector<int> E(n,n);
	for(int i:ps) for(int j:G[i]) E[j]=c;
	for(int i:p1) for(int j:G[i]) E[j]=-1;
	int sw=qry(E)-cts;
	return find(sw==p1.size()?p2:p1,ps,c,cts);
}
void work(){
	for(int i=0;i<n;i++){
		vector<int> E(n,n);
		for(int j=1;j<=n;j++) if(id[j]==j){
			if(op[j]==1){
				for(int h:G[j]) E[h-1]=i;
			}else{
				for(int h:G[j]) E[h-1]=-1;
			}
		}
		int w=qry(E);
		gdb(i,w,E[0],E[1],E[2],E[3]);
		vector<int> pos,ps;
		for(int j=1;j<=n;j++) if(fa[j]==j){
			if(op[j]==-1) pos.push_back(j);
			else ps.push_back(j);
		}
		while(1){
			int sw=w;
			fill(vis+1,vis+n+1,0);
			for(int j=1;j<=n;j++) if(fa[j]==j&&E[j-1]==i&&!vis[j]) sw--,dfs(j,i,E);
			if(sw==pos.size()) break;
			int p=find(pos,ps,i,w-sw);
			pos.erase(find(all(pos),p));
			ps.push_back(p);
			for(int j:G[p]) E[j-1]=i;col[p]=i;
		}
	}
}
vector<int> find_colours(int nn,vector<int> X,vector<int> Y) {
	n=nn;m=X.size();
	for(int i=0;i<m;i++){
		S[X[i]+1].push_back(Y[i]+1);
		S[Y[i]+1].push_back(X[i]+1);
	}
	iota(fa+1,fa+n+1,1);
	for(int i=1;i<=n;i++){
		vector<int> pos;
		for(int j:S[i])if(j<i){
			int flag=0;
			for(int h:pos) if(GF(h)==GF(j)) flag=1;
			if(!flag) pos.push_back(j);
		}
		if(pos.empty()) continue;
		vector<int> E(n,n);
		for(int j:pos) E[j-1]=-1;E[i-1]=-1;
		find_merge(pos,i,pos.size()+1-qry(E));
	}
	for(int i=1;i<=n;i++) G[GF(i)].push_back(i),id[i]=GF(i);
	for(int i=1;i<=n;i++) if(fa[i]==i&&!op[i]){
		op[i]=-1;
		for(int j:G[i]) for(int h:S[j]) op[id[h]]=1;
	}
	for(int i=1;i<=n;i++) if(fa[i]==i) gdb(i,op[i]);
	work();
	for(int i=1;i<=n;i++) if(fa[i]==i) op[i]*=-1;
	work();
	vector<int> ans(n);
	for(int i=1;i<=n;i++) ans[i-1]=col[GF(i)];
	return ans;
}