#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU{
int path[2020];
void init(int n){
for (int i=0;i<n;i++) path[i] = i;
}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
int merge(int x, int y){
x = find(x), y = find(y);
if (x==y) return 0;
path[x] = y;
return 1;
}
}dsu, dsu2;
int N;
vector<int> X, Y;
int query(vector<int> Q){
int ret = N;
dsu2.init(N);
for (int i=0;i<(int)X.size();i++){
if (Q[X[i]] >= 0 && Q[X[i]] == Q[Y[i]]) ret -= dsu2.merge(X[i], Y[i]);
if (Q[X[i]] == -1 && Q[Y[i]] == -1 && dsu.find(X[i]) == dsu.find(Y[i])) ret -= dsu2.merge(X[i], Y[i]);
}
ret -= perform_experiment(Q);
assert(ret >= 0);
return ret;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
::N = N, ::X = X, ::Y = Y;
dsu.init(N);
for (int i=0;i<N;i++){
vector<int> Q(N, N);
for (int j=0;j<=i;j++) Q[j] = -1;
int t = query(Q);
while(t--){
vector<int> adj;
for (int j=0;j<(int)X.size();j++){
int x = dsu.find(X[j]), y = dsu.find(Y[j]);
if (x == y) continue;
if (x == dsu.find(i) && y < i) adj.push_back(y);
if (x < i && y == dsu.find(i)) adj.push_back(x);
}
sort(adj.begin(), adj.end());
adj.erase(unique(adj.begin(), adj.end()), adj.end());
int l = 0, r = (int)adj.size() - 1, v = (int)adj.size();
while(l<=r){
int mid = (l+r)>>1;
vector<int> Q(N, N);
for (int j=0;j<N;j++){
if (dsu.find(j) == dsu.find(i)) Q[j] = -1;
if (find(adj.begin(), adj.end(), dsu.find(j)) - adj.begin() <= mid) Q[j] = -1;
}
if (query(Q) > 0) r = mid-1, v = mid;
else l = mid+1;
}
if (v == (int)adj.size()){
if (query(Q) == 0) return {};
}
assert(v < (int)adj.size());
dsu.merge(i, adj[v]);
}
}
vector<int> ret(N);
for (int i=0;i<N;i++) ret[i] = dsu.find(i);
return ret;
}
