#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> v[300];
int p[300], sz[300];
int p1[300], sz1[300];
int qan = 0;
//
void make_set1(int i)
{
p1[i] = i;
sz1[i] = 1;
}
int get_papa1(int i)
{
if(p1[i] == i)return i;
return p1[i] = get_papa1(p1[i]);
}
void union_set1(int a, int b)
{
a = get_papa1(a);
b = get_papa1(b);
if(a == b)return;
if(sz1[a] > sz1[b])swap(a, b);
p1[a] = b;
sz1[b] += sz1[a];
}
//
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++)
{
make_set1(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 = 1; i < N; i++)
{
int l = 0, r = i - 1, anss = -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 == bi[m])
{
anss= m;
r = m - 1;
}
else
l = m + 1;
}
if(anss != -1)
union_set1(i, anss);
}
for (int i = 0; i < N; i++)
{
ans.push_back(get_papa(i));
}
return ans;
}
