#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
int n;
vector<bool> visited;
vector<int> col;
vector<vector<int> > graph;
void dfs(int node){
visited[node]=1;
for (auto num:graph[node])if (!visited[num]&&col[num]==col[node])dfs(num);
}
int calc(){
visited.assign(n, 0);
int c=0;
for (int i=0; i<n; ++i)if (!visited[i])dfs(i), ++c;
return c;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y){
n=N;
col.resize(n, n);
graph.resize(n);
vector<int> ans(n, n);
for (int i=0; i<X.size(); ++i){
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
for (int i=0; i<n; ++i){
vector<int> temp(n);
temp[i]=-1;
col[i]=n-1;
for (int j=0; j<i; ++j)temp[j]=-1, col[j]=ans[j];
for (int j=i+1; j<n; ++j)temp[j]=col[j]=n;
int res=calc(), res2=perform_experiment(temp);
if (res==res2){
ans[i]=i;
continue;
}
set<int> merge;
for (int loop=0, p=-1; loop<res-res2; ++loop){
int low=p, high=i-1;
while (low+1<high){
int mid=(low+high)/2;
for (int j=0; j<n; ++j){
if (low<ans[j]&&ans[j]<=mid)temp[j]=-1, col[j]=ans[j];
else temp[j]=n, col[j]=n;
}
col[i]=n-1;
temp[i]=-1;
if (calc()==perform_experiment(temp))low=mid;
else high=mid;
}
merge.insert(high);
p=high;
}
ans[i]=*merge.begin();
for (int j=0; j<n; ++j)if (merge.find(ans[j])!=merge.end())ans[j]=*merge.begin();
}
return ans;
}
