#include "sphinx.h"
#include <bits/stdc++.h>
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
struct DSU {
vi p;
DSU(int n) : p(n, -1) {}
int find(int x) {
if (p[x] < 0) return x;
return p[x] = find(p[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (p[x] > p[y]) swap(x, y);
return p[x] += p[y], p[y] = x, true;
}
};
vector<vi> eraseEmpty(const vector<vi> &a) {
vector<vi> b;
for (auto v : a) if (!v.empty()) b.pb(v);
return b;
}
vi find_colours(int N, vi X, vi Y) {
vector<vi> adj(N);
forn(i, sz(X)) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
DSU dsu(N);
forsn(i, 1, N) {
vi E(N);
forn(j, N) E[j] = j <= i ? -1 : N;
auto expected = [&]() {
queue<int> q;
vector<bool> vis(N, false);
int cmps = 0;
forn(j, N) if (!vis[j]) {
q.push(j), cmps++, vis[j] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (vis[v]) continue;
if (E[u] != E[v]) continue;
if (E[u] == N || dsu.find(u) == dsu.find(v)) {
q.push(v), vis[v] = true;
}
}
}
}
return cmps;
};
while (true) {
vector<vi> comps(i);
for (int j : adj[i]) if (j < i) {
int p = dsu.find(j);
assert(p < i);
comps[p].pb(j);
}
comps = eraseEmpty(comps);
int lo = 0, hi = sz(comps) + 1;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
E = vi(N, N);
E[i] = -1;
forn(idx, mid) for (int j : comps[idx]) E[j] = -1;
if (perform_experiment(E) == expected()) {
lo = mid;
} else {
hi = mid;
}
}
if (lo < sz(comps)) dsu.unite(comps[lo].back(), i);
else break;
}
}
vi C(N);
forn(i, N) C[i] = dsu.find(i);
return C;
}
