#include "sphinx.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
struct Dsu
{
ll n, ans;
vector<ll> dsu;
Dsu(ll sz = 1)
{
n = sz;
ans = n;
dsu.resize(n + 1, -1);
init();
}
void init()
{
for (ll i = 1; i <= n; i++)
dsu[i] = -1;
}
bool Union(ll x, ll y)
{
x = repr(x), y = repr(y);
if (x == y)
return false;
if (dsu[x] < dsu[y])
swap(x, y);
ans--;
dsu[y] += dsu[x];
dsu[x] = y;
return true;
}
ll repr(ll x)
{
if (dsu[x] < 0)
return x;
return dsu[x] = repr(dsu[x]);
}
ll query()
{
return ans;
}
ll size(ll x)
{
return -dsu[repr(x)];
}
};
const ll N = 255;
bool g[N][N];
vector<int> send;
ll n;
ll compo()
{
Dsu dsu(n);
for (ll i = 0; i < n; i++)
for (ll j = i + 1; j < n; j++) if (g[i][j] and send[i] == n and send[j] == n) dsu.Union(i, j);
ll ans = 0;
for (ll i = 0; i < n; i++) if (send[i] == n) ans += dsu.repr(i) == i;
return ans;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y)
{
n = N;
for (ll i = 0; i < X.size(); i++)
g[X[i]][Y[i]] = g[Y[i]][X[i]] = 1;
Dsu dsu(n);
for (ll i = 0; i < n; i++)
{
vector<ll> adj;
{
set<ll> s;
for (ll j = 0; j < i; j++)
if (g[i][j] and !s.count(dsu.repr(j)))
adj.push_back(j), s.insert(dsu.repr(j));
}
for (ll ptr = 0; ptr < adj.size();)
{
ll l = ptr, r = adj.size() - 1, last = adj.size();
while (l <= r)
{
ll mid = (l + r) >> 1;
send = vector<int>(n, n);
for (ll i = 0; i <= mid; i++)
send[adj[i]] = -1;
send[i] = -1;
ll tot = compo() + 1;
for (ll j = 0; j < n; j++)
if (dsu.repr(j) != dsu.repr(i) and send[j] == -1)
tot++;
ll x = perform_experiment(send);
if (tot != x)
r = mid - 1, last = mid;
else
l = mid + 1;
}
if (last != adj.size())
dsu.Union(i, adj[last]);
ptr = last + 1;
}
}
vector<int> ans(n);
for (ll i = 0; i < n; i++) ans[i] = dsu.repr(i);
return ans;
}
