#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> v[300];
int p[300], sz[300];
int qan = 0;
void make_set(int i)
{
p[i] = i;
sz[i] = 1;
qan++;
}
int get_papa(int i)
{
if(p[i] == i)return i;
return p[i] = get_papa(p[i]);
}
void union_set(int a, int b)
{
a = get_papa(a);
b = get_papa(b);
if(a == b)return;
if(sz[a] > sz[b])swap(a, b);
p[a] = b;
sz[b] += sz[a];
qan--;
}
int NN;
vector<int> XX, YY;
int perform_experimentQ(vector<int> &a)
{
int x = perform_experiment(a);
qan = 0;
for (int i = 0; i < a.size(); i++)
{
if(a[i] == NN)
{
make_set(i);
}
}
for (int i = 0; i < XX.size(); i++)
{
if(a[XX[i]] == NN && a[YY[i]] == NN)
{
union_set(XX[i], YY[i]);
}
}
return x - qan;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
XX = X;
YY = Y;
NN = N;
if(N <= 50)
{
vector<int> G(N, 0);
vector<int> E(N, N);
for (int i = 0; i < X.size(); i++)
{
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
for (int i = 0; i < N; i++)
{
E[i] = 0;
E[v[i][0]] = 0;
int x = perform_experiment(E);
for (int j = 0; j < N; j++)
{
E[i] = -1;
E[v[i][0]] = j;
int y = perform_experiment(E);
if(x == y)
{
G[i] = j;
break;;
}
}
E[i] = N;
E[v[i][0]] = N;
}
return G;
}
vector<int> harc(N, N);
vector<int> bi;
for (int i = 0; i < N; i++)
{
harc[i] = -1;
if(i == 0)
bi.push_back(1);
else
bi.push_back(perform_experimentQ(harc));
}
int ne = 1;
vector<int> ans;
for (int i = 0; i < N; i++)
{
if(i == 0)
ans.push_back(0);
else
{
int st = 0;
if(harc[i] != harc[i - 1])
{
ans.push_back(ne);
ne++;
continue;
}
int l = 0, r = i - 2, anss = i - 1;
while(l <= r)
{
int m = (l + r) / 2;
vector<int> blblb(N, N);
for (int j = 0; j <= m; j++)
{
blblb[j] = -1;
}
blblb[i] = -1;
int x = perform_experimentQ(blblb);
if(x == harc[m])
{
anss= m;
r = m - 1;
}
else
l = m + 1;
}
ans.push_back(ans[anss]);
}
}
return ans;
}
