#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// generate random number between l, r : uniform_int_distribution<long long>(l, r)(rng)
// random shuffle : shuffle(.begin(), .end(), rng)
const int MAGIC_DEG = 32;
vector<int> find_colours(int n, vector<int> X, vector<int> Y) {
vector<vector<int>> g(n);
for (int i = 0; i < int(X.size()); i++) {
int u = X[i], v = Y[i];
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> color(n, -1);
vector<vector<int>> monochrome_graph(n);
function<void(int, int)> add_color = [&](int v, int col) {
if (color[v] != -1) {
assert(color[v] == col);
return;
}
color[v] = col;
for (int u : monochrome_graph[v]) {
add_color(u, col);
}
};
auto add_monochrome = [&](int u, int v) {
if (find(monochrome_graph[u].begin(), monochrome_graph[u].end(), v) != monochrome_graph[u].end()) return;
monochrome_graph[u].push_back(v);
monochrome_graph[v].push_back(u);
};
auto components_of_colored = [&](vector<int> coloring) {
dsu d(n);
int cnt = n;
for (int v = 0; v < n; v++) {
if (coloring[v] == -1) {
cnt--;
continue;
}
for (int u : g[v]) {
if (coloring[u] != coloring[v]) continue;
cnt -= d.unite(u, v);
}
}
return cnt;
};
for (int v = 0; v < n; v++) {
if (int(g[v].size()) > MAGIC_DEG) {
vector<int> adj_nodes = g[v];
vector<int> que_colors(n);
iota(que_colors.begin(), que_colors.end(), 0);
shuffle(que_colors.begin(), que_colors.end(), rng);
while (que_colors.size() > adj_nodes.size()) {
vector<int> try_color = vector<int>(que_colors.begin(), que_colors.begin() + adj_nodes.size());
que_colors.erase(que_colors.begin(), que_colors.begin() + adj_nodes.size());
vector<int> coloring(n, n);
coloring[v] = -1;
for (int i = 0; i < int(adj_nodes.size()); i++) {
coloring[adj_nodes[i]] = try_color[i];
}
int comp_with_unique_v = components_of_colored(coloring) + 1;
int comp_with_monochromable_v = perform_experiment(coloring);
assert(comp_with_unique_v >= comp_with_monochromable_v);
bool monochrome_reduce_comp = comp_with_unique_v > comp_with_monochromable_v;
if (monochrome_reduce_comp) que_colors = try_color;
}
while (que_colors.size() > 1) {
int sz = que_colors.size();
vector<int> Left_colors = vector<int>(que_colors.begin(), que_colors.begin() + sz / 2);
vector<int> coloring(n, n);
coloring[v] = -1;
for (int i = 0; i < int(Left_colors.size()); i++) {
coloring[adj_nodes[i]] = Left_colors[i];
}
int comp_with_unique_v = components_of_colored(coloring) + 1;
int comp_with_monochromable_v = perform_experiment(coloring);
assert(comp_with_unique_v >= comp_with_monochromable_v);
bool monochrome_reduce_comp = comp_with_unique_v > comp_with_monochromable_v;
if (monochrome_reduce_comp) {
que_colors = Left_colors;
} else {
que_colors = vector<int>(que_colors.begin() + sz / 2, que_colors.end());
}
}
assert(que_colors.size() == 1);
add_color(v, que_colors[0]);
}
}
vector<int> process_order(n);
iota(process_order.begin(), process_order.end(), 0);
sort(process_order.begin(), process_order.end(), [&](int i, int j){return color[i] > color[j];});
vector<bool> processed(n);
dsu forest_spanning_monochrome(n);
vector<int> current_roots;
for (int v : process_order) {
if (color[v] != -1) {
vector<int> same_color_adj;
for (int u : g[v]) {
if (!processed[u]) continue;
if (color[u] == color[v]) {
same_color_adj.push_back(u);
}
}
for (int u : same_color_adj) {
int ru = forest_spanning_monochrome.get(u);
auto it = find(current_roots.begin(), current_roots.end(), ru);
if (it == current_roots.end()) continue;
forest_spanning_monochrome.unite(ru, v);
current_roots.erase(it);
add_monochrome(u, v);
}
current_roots.push_back(v);
} else {
vector<int> adj_nodes_unique_color_root;
for (int u : g[v]) {
if (!processed[u]) continue;
bool Unique = true;
for (int w : g[v]) {
if (w == u) break;
if (!processed[w]) continue;
if (forest_spanning_monochrome.get(w) == forest_spanning_monochrome.get(u)) {
Unique = false;
break;
}
}
if (Unique) adj_nodes_unique_color_root.push_back(u);
}
vector<int> same_color_adj_nodes;
function<void(vector<int>, int)> dfs = [&](vector<int> possible_same_color_adj_nodes, int total_same_color) {
if (total_same_color == 0) return;
int sz = possible_same_color_adj_nodes.size();
if (total_same_color == sz) {
for (int nd : possible_same_color_adj_nodes) same_color_adj_nodes.push_back(nd);
return;
}
vector<int> coloring(n, n);
coloring[v] = -1;
for (int i = 0; i < sz / 2; i++) {
coloring[possible_same_color_adj_nodes[i]] = -1;
}
int Left_connected_nodes = components_of_colored(coloring) + sz / 2 + 1 - perform_experiment(coloring);
int Right_connected_nodes = total_same_color - Left_connected_nodes;
dfs(vector<int>(possible_same_color_adj_nodes.begin(), possible_same_color_adj_nodes.begin() + sz / 2), Left_connected_nodes);
dfs(vector<int>(possible_same_color_adj_nodes.begin() + sz / 2, possible_same_color_adj_nodes.end()), Right_connected_nodes);
};
vector<int> coloring(n, n);
coloring[v] = -1;
for (int i : adj_nodes_unique_color_root) coloring[i] = -1;
int total_same_color = components_of_colored(coloring) + adj_nodes_unique_color_root.size() + 1 - perform_experiment(coloring);
dfs(adj_nodes_unique_color_root, total_same_color);
for (int nd : same_color_adj_nodes) {
add_monochrome(nd, v);
nd = forest_spanning_monochrome.get(nd);
auto it = find(current_roots.begin(), current_roots.end(), nd);
if (it == current_roots.end()) continue;
current_roots.erase(it);
forest_spanning_monochrome.unite(nd, v);
}
for (int nd : same_color_adj_nodes) {
if (color[nd] != -1) {
assert(color[v] == -1 || color[v] == color[nd]);
add_color(v, color[nd]);
}
}
current_roots.push_back(v);
}
processed[v] = true;
}
vector<int> choose(n);
while (true) {
bool change = false;
for (int v = 0; v < n; v++) {
int bal = 0;
for (int u : g[v]) {
if (choose[u] == (choose[v] ^ 1)) {
bal += 1;
} else {
bal -= 1;
}
}
if (bal < 0) {
choose[v] ^= 1;
change = true;
}
}
if (!change) break;
}
vector<vector<int>> Total_adj_batch(2);
for (int v = 0; v < n; v++) Total_adj_batch[choose[v]].push_back(v);
for (int rot = 0; rot < 2; rot++) {
vector<int> Seekers;
vector<int> Helpers = Total_adj_batch[rot ^ 1];
for (int v : Total_adj_batch[rot]) {
if (color[v] == -1 && forest_spanning_monochrome.get(v) == v) Seekers.push_back(v);
}
if (Seekers.empty()) continue;
for (int col = 0; col < n; col++) {
if (Seekers.empty()) break;
vector<int> colled;
function<void(vector<int>, int, int)> dfs = [&](vector<int> Candidates, int col_spanning_edges, int so_far) {
if (col_spanning_edges == 0) return;
if (Candidates.size() == 1) {
assert(so_far <= 7);
colled.push_back(Candidates[0]);
return;
}
int sz = Candidates.size();
vector<int> coloring(n, n);
for (int v : Helpers) coloring[v] = col;
for (int i = 0; i < sz / 2; i++) coloring[Candidates[i]] = -1;
int Left_col_spanning_edges = components_of_colored(coloring) + sz / 2 - perform_experiment(coloring);
bool is_right_needed = col_spanning_edges > Left_col_spanning_edges;
int Right_col_spanning_edges = 0;
if (is_right_needed) {
if (Left_col_spanning_edges > 0) {
for (int i = 0; i < sz / 2; i++) coloring[Candidates[i]] = n;
for (int i = sz / 2; i < sz; i++) coloring[Candidates[i]] = -1;
Right_col_spanning_edges = components_of_colored(coloring) + sz - sz / 2 - perform_experiment(coloring);
assert(Right_col_spanning_edges > 0);
} else {
Right_col_spanning_edges = col_spanning_edges;
}
}
assert(Left_col_spanning_edges > 0 || Right_col_spanning_edges > 0);
dfs(vector<int>(Candidates.begin(), Candidates.begin() + sz / 2), Left_col_spanning_edges, so_far + 1);
dfs(vector<int>(Candidates.begin() + sz / 2, Candidates.end()), Right_col_spanning_edges, so_far + 1);
};
vector<int> coloring(n, n);
for (int v : Seekers) coloring[v] = -1;
for (int v : Helpers) coloring[v] = col;
int col_spanning_edges = components_of_colored(coloring) + Seekers.size() - perform_experiment(coloring);
dfs(Seekers, col_spanning_edges, 0);
for (int v : colled) {
add_color(v, col);
Seekers.erase(find(Seekers.begin(), Seekers.end(), v));
}
}
assert(Seekers.empty());
}
assert(count(color.begin(), color.end(), -1) == 0);
return color;
}
