#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 外部声明，交互库提供
int perform_experiment(std::vector<int> E);
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
int M = X.size();
vector<vector<int>> adj(N);
vector<vector<bool>> is_adj(N, vector<bool>(N, false));
for (int i = 0; i < M; ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
is_adj[X[i]][Y[i]] = true;
is_adj[Y[i]][X[i]] = true;
}
auto get_K = [&](const vector<int>& Y_set) {
vector<bool> in_Y(N, false);
for (int y : Y_set) in_Y[y] = true;
vector<bool> vis(N, false);
int K = 0;
for (int i : Y_set) {
if (!vis[i]) {
K++;
queue<int> q;
q.push(i);
vis[i] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (in_Y[v] && !vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
}
return K;
};
// 阶段一：寻找单色连通分支
vector<vector<int>> components;
components.push_back({0});
auto query_part1 = [&](const vector<vector<int>>& S, int i) {
vector<int> E(N, N);
vector<int> Y_set;
vector<bool> in_VS(N, false);
for (const auto& comp : S) {
for (int v : comp) {
E[v] = -1;
in_VS[v] = true;
}
}
E[i] = -1;
in_VS[i] = true;
for (int v = 0; v < N; ++v) {
if (!in_VS[v]) Y_set.push_back(v);
}
int K = get_K(Y_set);
int Q = perform_experiment(E);
return Q <= (int)S.size() + K;
};
auto bin_search_part1 = [&](const vector<vector<int>>& S, int i) {
int low = 0, high = S.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
vector<vector<int>> left_half(S.begin() + low, S.begin() + mid + 1);
if (query_part1(left_half, i)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
};
for (int i = 1; i < N; ++i) {
vector<vector<int>> adj_comps;
vector<int> adj_comps_idx;
for (int c = 0; c < components.size(); ++c) {
bool adj_flag = false;
for (int v : components[c]) {
if (is_adj[i][v]) { adj_flag = true; break; }
}
if (adj_flag) {
adj_comps.push_back(components[c]);
adj_comps_idx.push_back(c);
}
}
vector<int> match_idxs;
while (!adj_comps.empty()) {
if (!query_part1(adj_comps, i)) break;
int match_local = bin_search_part1(adj_comps, i);
match_idxs.push_back(adj_comps_idx[match_local]);
adj_comps.erase(adj_comps.begin() + match_local);
adj_comps_idx.erase(adj_comps_idx.begin() + match_local);
}
vector<int> new_comp = {i};
sort(match_idxs.rbegin(), match_idxs.rend());
for (int idx : match_idxs) {
for (int v : components[idx]) new_comp.push_back(v);
components.erase(components.begin() + idx);
}
components.push_back(new_comp);
}
// 阶段二：计算单色连通分支的绝对颜色
int B = components.size();
vector<int> final_colors(N, -1);
if (B == 1) { // 边界处理：全图属于同一种颜色
int color = 0;
for (int c = 0; c < N; ++c) {
vector<int> E(N, c);
E[0] = -1;
if (perform_experiment(E) == 1) { color = c; break; }
}
for (int i = 0; i < N; ++i) final_colors[i] = color;
return final_colors;
}
vector<vector<int>> branch_adj(B);
for (int i = 0; i < B; ++i) {
for (int j = i + 1; j < B; ++j) {
bool edge = false;
for (int u : components[i]) {
for (int v : components[j]) {
if (is_adj[u][v]) { edge = true; break; }
}
if (edge) break;
}
if (edge) {
branch_adj[i].push_back(j);
branch_adj[j].push_back(i);
}
}
}
vector<int> dist(B, -1);
queue<int> q;
q.push(0);
dist[0] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : branch_adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
vector<int> S1, S2;
for (int i = 0; i < B; ++i) {
if (dist[i] % 2 == 0) S1.push_back(i);
else S2.push_back(i);
}
auto query_part2 = [&](const vector<int>& S, int c) {
vector<int> E(N, c);
vector<int> Y_set;
vector<bool> in_S(N, false);
for (int b : S) {
for (int v : components[b]) {
E[v] = -1;
in_S[v] = true;
}
}
for (int v = 0; v < N; ++v) {
if (!in_S[v]) Y_set.push_back(v);
}
int K = get_K(Y_set);
int Q = perform_experiment(E);
return Q < (int)S.size() + K;
};
auto bin_search_part2 = [&](const vector<int>& S, int c) {
int low = 0, high = S.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
vector<int> left_half(S.begin() + low, S.begin() + mid + 1);
if (query_part2(left_half, c)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
};
int colored_branches = 0;
vector<int> branch_color(B, -1);
for (int c = 0; c < N; ++c) {
if (colored_branches == B) break; // 若全部匹配提前收工
// 扫 S1
vector<int> cur_S1;
for (int b : S1) if (branch_color[b] == -1) cur_S1.push_back(b);
while (!cur_S1.empty()) {
if (!query_part2(cur_S1, c)) break;
int idx = bin_search_part2(cur_S1, c);
branch_color[cur_S1[idx]] = c;
colored_branches++;
cur_S1.erase(cur_S1.begin() + idx);
}
if (colored_branches == B) break;
// 扫 S2
vector<int> cur_S2;
for (int b : S2) if (branch_color[b] == -1) cur_S2.push_back(b);
while (!cur_S2.empty()) {
if (!query_part2(cur_S2, c)) break;
int idx = bin_search_part2(cur_S2, c);
branch_color[cur_S2[idx]] = c;
colored_branches++;
cur_S2.erase(cur_S2.begin() + idx);
}
}
for (int i = 0; i < B; ++i) {
for (int v : components[i]) {
final_colors[v] = branch_color[i];
}
}
return final_colors;
}
