#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef int ll;
namespace{
const ll mxN=255;
ll n, m;
// vll adj[mxN];
vll adj2[mxN];
bool visited[mxN];
bool done[mxN];
vll tep, ans;
ll timer;
bool adj[mxN][mxN];
void dfs(ll cur, ll u){
if(cur==u || visited[cur]) return;
visited[cur]=1;
for(ll i=0;i<n;i++){
if(adj[cur][i]){
if(tep[cur]==n && tep[i]==n){
dfs(i, u);
}
else if(tep[cur]==-1 && tep[i]==-1 && ans[cur]==ans[i]){
dfs(i, u);
}
}
}
}
void dfs2(ll cur, ll a){
if(done[cur]) return;
done[cur]=1;
ans[cur]=a;
for(auto &it:adj2[cur]){
dfs2(it, a);
}
}
ll f(ll u){
memset(visited, 0, sizeof(visited));
ll cnt=0;
for(ll i=0;i<n;i++){
if(i==u) continue;
if(!visited[i]){
dfs(i, u);
cnt++;
}
}
return cnt;
}
ll ceil_div(ll a, ll b){
return (a+b-1)/b;
}
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
memset(done, 0, sizeof(done));
memset(adj, 0, sizeof(adj));
n=N;
m=X.size();
for(ll i=0;i<m;i++){
adj[X[i]][Y[i]]=1;;
adj[Y[i]][X[i]]=1;
}
ans=vll(n, -1);
timer=0;
auto qry=[&](ll u, ll tar){
tep=vll(n, n);
tep[u]=-1;
for(ll i=u+1;i<n;i++){
if(adj[u][i] && i<=tar && !done[i]){
tep[i]=-1;
}
}
if(perform_experiment(tep)==f(u)+1){
return false;
}
return true;
};
for(ll i=n-1;i>=0;i--){
memset(done, 0, sizeof(done));
ans[i]=i;
while(true){
vll v;
for(ll j=i+1;j<n;j++){
if(adj[i][j] && !done[j]){
v.pb(j);
}
}
if(v.empty()) break;
ll lef=0, rig=(ll) v.size()-1;
ll good=-1;
if(!qry(i, v[rig])){
break;
}
while(lef<=rig){
ll mid=(lef+rig)/2;
if(qry(i, v[mid])){
good=mid;
rig=mid-1;
}
else{
lef=mid+1;
}
}
assert(good!=-1);
dfs2(v[good], ans[i]);
adj2[i].pb(v[good]);
adj2[v[good]].pb(i);
}
}
// cout<<qry(1, 0)<<'\n';
return ans;
}
