#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
int perform_experiment(vector<int> E);
int n , was[N] , check[N] , p[N];
vector<int> g[N] , ord;
int gett(int x){
if(p[x] == x) return x;
return p[x] = gett(p[x]);
}
int merge(int a, int b){
a = gett(a);
b = gett(b);
if(a == b) return 0 ;
p[a] = b;
return 1;
}
void dfs(int x) {
was[x] = true;
for (int i : g[x]) {
if (!was[i] && ord[x] == ord[i]) dfs(i);
}
}
int expected(int n) {
for (int i = 0; i < n; i++) was[i] = false;
int sum = 0;
for (int i = 0; i < n; i++) {
if (ord[i] == -1) {
sum++;
} else if (!was[i]) {
sum++;
dfs(i);
}
}
return sum;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
vector<vector<int>> comps;
comps.push_back({0});
for (int i = 1; i < N; ++i) {
vector<int> ord(N, -1);
for (int j = i + 1; j < N; ++j) ord[j] = N;
if (perform_experiment(ord) == (int)comps.size() + 1 + (i + 1 < N)) {
comps.push_back({i});
continue;
}
int lo = 0, hi = comps.size();
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
ord.assign(N, N);
ord[i] = -1;
for (int c = mid; c < hi; ++c) {
for (int u : comps[c]) {
ord[u] = -1;
}
}
int expected = 2 + hi - mid;
if (perform_experiment(ord) < expected) {
lo = mid;
} else {
hi = mid;
}
}
comps[lo].push_back(i);
}
vector<int> F(N, -1);
for (int c = 0; c < (int)comps.size(); ++c) {
for (int u : comps[c]) {
F[u] = c;
}
}
return F;
}
