#include "sphinx.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 500 + 100 , inf = 1e9 , mod = 998244353;
vector <int> vec[maxn] , G[maxn] ;
int par[maxn] , mark[maxn] , n;
vector <int> y;
void dfs(int v){
mark[v] =1 ;
for(int u : G[v]){
if(y[u] == n && mark[u] == 0)dfs(u);
}
}
int que(vector <int> x){
int sm =perform_experiment(x);
y =x;
rep(i ,0 , n-1){
mark[i] =0 ;
}
rep(i ,0, n-1){
if(mark[i] ==0 && x[i] == n){
dfs(i) ;
sm-- ;
}
}
return sm ;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
n = N;
rep(i , 0 ,sz(X)-1){
G[X[i]].pb(Y[i]);
G[Y[i]].pb(X[i]);
}
rep(i , 0 ,n-1)vec[i].pb(i);
vector<int> az ;
rep(i , 0 , n-1){
vector <int> e ;
rep(j , 0 ,n-1){
if(j > i){
e.pb(n);
continue ;
}
e.pb(-1);
}
if(que(e) == 1 + sz(az)){
az.pb(i) ;
continue ;
}
int l =-1 , r = sz(az)-1;
while(r-l > 1){
int m = (l+r)/2 ;
vector <int> e ;
rep(i , 0 ,n-1)e.pb(n) ;
e[i] = -1 ;
rep(i , 0 ,m){
int x = az[i] ;
for(int y : vec[x]){
e[y] = -1 ;
}
}
if(que(e) == 1 + (m+1)){
l = m;
}else{
r = m ;
}
}
vec[az[r]].pb(i) ;
}
int cnt = 0;
vector <int> ans ;
rep(i , 0 ,n-1)ans.pb(0);
for(int x : az){
for(int y : vec[x]){
ans[y] = cnt ;
}
cnt++ ;
}
return ans ;
}
