#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
vector<int> a;
vector<int> colors;
vector<int> fakecolors;
vector<vector<int>> graf;
int n;
//ll perform_experiment(vector<int> a) {return 0;}
void dfs(ll v, vb& visited){
visited[v] = true;
for (auto x : graf[v]){
if (visited[x] == false && fakecolors[v] == fakecolors[x]){
dfs(x, visited);
}
}
return;
}
ll components(){
vb visited(n, false);
ll c = 0;
for (ll i = 0; i < n; i++){
c++;
dfs(i, visited);
}
return c;
}
std::vector<int> find_colours(int N,
std::vector<int> X, std::vector<int> Y){
n = N;
graf.resize(n);
colors.resize(n, n);
fakecolors.resize(n,n);
for (int i = 0; i < n; i++){
a.push_back(n);
}
for (int i = 0; i < X.size(); i++){
graf[X[i]].push_back(Y[i]);
graf[Y[i]].push_back(X[i]);
}
for (ll i = 0; i < n; i++){
fakecolors[i] = n-1; a[i] = n-1;
for (ll j = 0; j < i; j++){
a[j] = -1;
fakecolors[j] = colors[j];
}
for (ll j = i+1; j < n; j++){
a[j] = n;
fakecolors[j] = n;
}
ll estimate = components();
ll real = perform_experiment(a);
if (estimate == real){
colors[i] = i;
continue;
}
ll last = -1;
set<ll> found;
for (ll d = 0; d < estimate-real; d++){
ll l = last+1; ll r = i-1; ll mid = 0;
while (l <= r){
mid = (l+r)/2;
//Recolor all in mid+1-r to N, if estimate == real, then wrong half
// get component color, start binary search again from that component to r, get another...
// recolor all these components to first of those.
for (ll j = 0; j < n; j++){
if (l <= j && j <= mid){
fakecolors[j] = colors[j];
a[j] = -1;
}
else{
fakecolors[j] = n;
a[j] = n;
}
}
fakecolors[i] = n-1; a[i] = -1;
ll nest = components();
ll nrea = perform_experiment(a);
if (nest == nrea){
l = mid+1;
}
else{
r = mid;
}
}
last = l;
found.insert(l);
}
ll finalcolor = *found.begin();
colors[i] = finalcolor;
for (ll j = 0; j < n; j++){
auto it = found.find(colors[j]);
if (it != found.end()){
colors[j] = finalcolor;
}
}
}
return colors;
}
