#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
vector<bool> visited;
vector<int> dsu, ord;
vector<vector<int> > graph;
int fp(int a){
if (dsu[a]==-1)return a;
return dsu[a]=fp(dsu[a]);
}
void merge(int a, int b){
a=fp(a), b=fp(b);
if (a!=b)dsu[a]=b;
}
void dfs(int node){
ord.pb(node);
visited[node]=1;
for (auto num:graph[node])if (!visited[num])dfs(num);
}
vector<int> find_colours(int n, vector<int> X, vector<int> Y){
dsu.resize(n, -1);
graph.resize(n);
visited.resize(n, 0);
for (int i=0; i<X.size(); ++i){
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
dfs(0);
vector<int> vect(1, 0), ans(n);
for (int i=1; i<n; ++i){
vector<int> temp(n, n);
set<int> uq;
for (int j=0; j<=i; ++j)temp[ord[j]]=-1, uq.insert(fp(ord[j]));
int res=perform_experiment(temp);
if (res>uq.size()){
vect.pb(i);
continue;
}
int low=-1, high=vect.size()-1;
while (low+1<high){
int mid=(low+high)/2;
vector<int> temp(n, n), can(n, 0), gan(n, 0);;
for (int j=low+1; j<=mid; ++j)can[fp(vect[j])]=1;
set<int> uq;
for (auto num:graph[ord[i]])if (can[fp(num)])uq.insert(fp(num)), gan[fp(num)]=1;
temp[ord[i]]=-1;
for (int j=0; j<i; ++j)if (gan[fp(ord[j])])temp[ord[j]]=-1;
if (perform_experiment(temp)==uq.size())high=mid;
else low=mid;
}
merge(ord[i], vect[high]);
}
for (int i=0; i<n; ++i)ans[i]=fp(i);
return ans;
}
