#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define trace(x) for (auto &el : x) cerr << el << " "
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
vi find_complete(int n, vi X, vi Y) {
vi G(n, 0);
auto first_k_colours = [&](int target, int k) {
if (k >= n) {
vi e(n, n-1); e[target] = 1;
return e;
}
vi e(n, n); e[target] = -1;
int colour = 0;
for (int i = 0; i < target && k > 0; i++) {
e[i] = colour;
k--; colour++;
}
for (int i = target + 1; i < n && k > 0; i++) {
e[i] = colour;
k--; colour++;
}
return e;
};
auto expected_cmps = [](vi experiment) {
int sc = 0; for (auto el : experiment) if (el == -1) sc++;
int sz = set<int>(experiment.begin(), experiment.end()).size();
if (sc > 0) sz = sz - 1 + sc;
return sz;
};
for (int i = 0; i < n; i++) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi e = first_k_colours(i, mid);
int x = perform_experiment(e);
if (x == expected_cmps(e)) {
lo = mid + 1;
} else {
hi = mid;
}
}
G[i] = lo - 1;
}
return G;
}
/*
for the case of the graph being a path:
divide the graph into two disjoint sets ie. XYXYXY
for each colour, determine for each set X and Y how many elements in the entire graph have colour c
do this by setting all nodes of the other set to colour c then computing #(expected cmps) - #(actual cmps)
takes 2n = 500 queries
now for each colour that appears t > 0 times in a set, launch t binary searches of the form (first node where c appears >= i times?)
for i in range [1, t]
the sum of #(appearances in set) over all colours with t>0 is = size of set = n/2
in total doing this process for both sets will take 2 * (n/2) binary searches that use log₂(n/2) queries each, or for n = 250
it uses 2 * 125 * 7 = 1750 queries
in total 1750 + 500 = 2250
*/
vi find_path(int n, vi X, vi Y) {
vi G(n, 0);
auto expected_cmps = [&](vi e) {
int sz = 1; for (int i = 1; i < n; i++) if (!(e[i] == e[i-1] && e[i] != -1)) sz++;
return sz;
};
auto f = [&](int k, int colour, bool set1) {
vi e(n, n);
int LC = set1 ? -1 : colour, RC = set1 ? colour : -1;
for (int i = 0; i < k && (2*i) < n; i++) {
e[2*i] = LC;
if (2*i+1 < n) e[2*i+1] = RC;
}
return e;
};
auto g = [&](vi base, int colour, vi indices) {
for (auto el : indices) if (base[el] != n) base[el] = colour;
return base;
};
// set 1 is U.U.U.U., set2 is .V.V.V.V
int s1 = n/2, s2 = (n)/2;
for (int c = 0; c < n; c++) {
vi e1 = f(s1, c, true), e2 = f(s2, c, false);
int x1 = perform_experiment(e1), x2 = perform_experiment(e2);
if (x1 != expected_cmps(e1)) {
vi found;
while (expected_cmps(g(f(s1, c, true), c, found)) != x1) {
int lo = 0, hi = s1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi e = g(f(mid, c, true), c, found);
if (perform_experiment(e) == expected_cmps(e)) {
lo = mid + 1;
} else {
hi = mid;
}
}
found.push_back(2*(lo-1));
G[2*(lo-1)] = c;
}
}
if (x2 != expected_cmps(e2)) {
vi found;
while (expected_cmps(g(f(s2, c, false), c, found)) != x2) {
int lo = 0, hi = s2;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi e = g(f(mid, c, false), c, found);
if (perform_experiment(e) == expected_cmps(e)) {
lo = mid + 1;
} else {
hi = mid;
}
}
found.push_back(2*lo-1);
G[2*lo-1] = c;
}
}
if (n % 2 == 1) {
vi e(n, n);
e[n-2] = c; e[n-1] = -1;
if (perform_experiment(e) == 2) {
G[n-1] = c;
}
}
}
return G;
}
vi find_small(int n, vi X, vi Y) {
vi G(n, 0);
for (int i = 0; i < n; i++) {
for (int c = 0; c < n; c++) {
vi e(n, c); e[i] = -1;
if (perform_experiment(e) == 1) G[i] = c;
}
}
return G;
}
struct DSU {
int n, cmps; vi par;
DSU() {};
DSU(int N) {
n = cmps = N; for (int i = 0; i < n; i++) par.push_back(i);
}
int find(int v) {
if(par[v] == v) return v;
return par[v] = find(par[v]);
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
par[b] = a;
cmps--;
}
}
};
int count_expected(int n, vi X, vi Y, vi e) {
auto dsu = DSU(n);
for (int i = 0; i < X.size(); i++) {
if (e[X[i]] != e[Y[i]] || e[X[i]] == -1 || e[Y[i]] == -1) continue;
dsu.unite(X[i], Y[i]);
}
return dsu.cmps;
}
vi find_general(int n, vi X, vi Y) {
vector<vi> adj(n, vi()); for (int i = 0; i < X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vi G(n, 0), order;
queue<int> q({0}); G[0] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (auto v : adj[u]) {
if (G[v]) continue;
q.push(v); G[v]++;
}
}
G.assign(n, -1); G[0] = 0;
vector<vi> cmps(1, vi(1, 0));
for (auto u : order) {
if (u == 0) continue;
int lo = 0, hi = cmps.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi e(n, n); e[u] = -1; for (int i = 0; i <= mid; i++) for (auto el : cmps[i]) e[el] = i;
int x = count_expected(n, X, Y, e); for (int i = 0; i <= mid; i++) for (auto el : cmps[i]) e[el] = -1;
if (x == perform_experiment(e)) {
lo = mid + 1;
} else {
hi = mid;
}
}
if (lo >= cmps.size()) {
cmps.push_back(vi({u}));
} else {
cmps[lo].push_back(u);
}
}
for (int i = 0; i < cmps.size(); i++) for (auto el : cmps[i]) G[el] = i;
return G;
}
vi find_colours(int n, vi X, vi Y) {
// if (X.size() == (n * (n-1) / 2)) {
// return find_complete(n, X, Y);
// } else if (n <= 50) {
// return find_small(n, X, Y);
// } else if (X.size() == n-1) {
// return find_path(n, X, Y);
// }
vi G = find_general(n, X, Y);
return G;
}
