#include "sphinx.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 255;
int n, m;
int same[maxn];
vector < int > g[maxn];
int used[maxn], a[maxn];
void dfs(int beg)
{
used[beg] = 1;
for (auto nb: g[beg])
{
if(used[nb])continue;
if(a[nb] != n)continue;
dfs(nb);
}
}
int col[maxn];
int dp[maxn];
int ask(int mid, int curr)
{
vector < int > g;
int is = 0;
for (int i = 0; i < n; ++ i)
{
if(i <= mid)g.pb(-1);
else if(i == curr)g.pb(-1);
else
{
is = 1;
g.pb(n);
}
}
int ans = perform_experiment(g);
return ans-is;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y)
{
n = N;
m = X.size();
for (int i = 0; i < m; ++ i)
{
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
dp[0] = 1;
col[0] = 0;
int mx = 0;
for (int i = 1; i < n; ++ i)
{
// vector < int >
int l = 0, r = i-1, mid, ans = i; /// pyrvoto obyrkano
while(l <= r)
{
mid = (l + r)/2;
int fb = ask(mid, i);
if(fb == dp[mid])
{
r = mid - 1;
ans = mid;
}
else
{
l = mid+1;
}
}
// cout << ans << endl;
if(ans == i)
{
mx ++;
dp[i] = dp[i-1] + 1;
col[i] = mx;
}
else
{
dp[i] = dp[i-1];
col[i] = col[ans];
}
// cout << "dp is " << i << " " << dp[i] << endl;
}
vector < int > res;
for (int i = 0; i < n; ++ i)
res.pb(col[i]);
return res;
/*std::vector<int> e(N, -1);
for (int i = 0; i < n-1; ++ i)
{
vector < int > g;
int pre = 0, post = 0;
for (int j = 0; j < i; ++ j)
{
g.pb(n);
pre = 1;
}
g.pb(-1);
g.pb(-1);
for (int j = i+2; j < n; ++ j)
{
g.pb(n);
post = 1;
}
int fb = perform_experiment(g);
if(fb == pre + post + 1)same[i+1] = 1;
else same[i+1] = 0;
}
// vector< int > res;
res.pb(0);
int curr = 0;
for (int i = 1; i < n; ++ i)
{
if(same[i])res.pb(curr);
else
{
curr ++;
res.pb(curr);
}
}
*/
return res;
}
