// Grafos no dirigidos simples y las fuerzas brutas que sirven de referencia en esta semana.
#pragma once
#include <algorithm>
#include <cstddef>
#include <optional>
#include <utility>
#include <vector>

using Graph = std::vector<std::vector<int>>;

inline void add_edge(Graph& g, int u, int v) {
    g[static_cast<std::size_t>(u)].push_back(v);
    g[static_cast<std::size_t>(v)].push_back(u);
}

inline Graph make_graph(int n, const std::vector<std::pair<int, int>>& edges) {
    Graph g(static_cast<std::size_t>(n));
    for (auto [u, v] : edges) add_edge(g, u, v);
    return g;
}

inline std::vector<std::pair<int, int>> edge_list(const Graph& g) {
    std::vector<std::pair<int, int>> edges;
    for (std::size_t u = 0; u < g.size(); u++) {
        for (int v : g[u]) {
            if (static_cast<int>(u) < v) edges.push_back({static_cast<int>(u), v});
        }
    }
    return edges;
}

inline std::size_t edge_count(const Graph& g) {
    std::size_t total = 0;
    for (const auto& list : g) total += list.size();
    return total / 2;
}

// Verificadores: el certificado es el conjunto, y se revisa en tiempo polinomial.
inline bool is_independent(const Graph& g, const std::vector<int>& nodes) {
    std::vector<char> inside(g.size(), 0);
    for (int v : nodes) {
        if (inside[static_cast<std::size_t>(v)]) return false;
        inside[static_cast<std::size_t>(v)] = 1;
    }
    for (int v : nodes) {
        for (int w : g[static_cast<std::size_t>(v)]) {
            if (inside[static_cast<std::size_t>(w)]) return false;
        }
    }
    return true;
}

inline bool is_cover(const Graph& g, const std::vector<int>& nodes) {
    std::vector<char> inside(g.size(), 0);
    for (int v : nodes) inside[static_cast<std::size_t>(v)] = 1;
    for (auto [u, v] : edge_list(g)) {
        if (!inside[static_cast<std::size_t>(u)] && !inside[static_cast<std::size_t>(v)]) return false;
    }
    return true;
}

inline bool is_proper_coloring(const Graph& g, const std::vector<int>& color, int colors) {
    for (std::size_t u = 0; u < g.size(); u++) {
        if (color[u] < 0 || color[u] >= colors) return false;
        for (int v : g[u]) {
            if (color[u] == color[static_cast<std::size_t>(v)]) return false;
        }
    }
    return true;
}

// Conjunto independiente máximo: en cada nodo, tomarlo o no. Exponencial; solo para grafos pequeños.
inline void independent_search(const Graph& g, std::size_t v, std::vector<int>& blocked, std::vector<int>& current,
                               std::vector<int>& best) {
    if (current.size() + (g.size() - v) <= best.size()) return;
    if (v == g.size()) {
        best = current;
        return;
    }
    if (blocked[v] == 0) {
        for (int w : g[v]) blocked[static_cast<std::size_t>(w)]++;
        current.push_back(static_cast<int>(v));
        independent_search(g, v + 1, blocked, current, best);
        current.pop_back();
        for (int w : g[v]) blocked[static_cast<std::size_t>(w)]--;
    }
    independent_search(g, v + 1, blocked, current, best);
}

inline std::vector<int> max_independent_set(const Graph& g) {
    std::vector<int> blocked(g.size(), 0);
    std::vector<int> current;
    std::vector<int> best;
    independent_search(g, 0, blocked, current, best);
    return best;
}

// Cobertura mínima, probando los 2^V subconjuntos.
inline std::vector<int> min_vertex_cover(const Graph& g) {
    const std::size_t n = g.size();
    std::vector<int> best;
    for (std::size_t i = 0; i < n; i++) best.push_back(static_cast<int>(i));
    for (unsigned long long mask = 0; mask < (1ULL << n); mask++) {
        std::vector<int> nodes;
        for (std::size_t i = 0; i < n; i++) {
            if ((mask >> i) & 1) nodes.push_back(static_cast<int>(i));
        }
        if (nodes.size() < best.size() && is_cover(g, nodes)) best = nodes;
    }
    return best;
}

// Backtracking para colorear con k colores, nodo por nodo.
inline bool color_search(const Graph& g, std::size_t v, int k, std::vector<int>& color) {
    if (v == g.size()) return true;
    for (int c = 0; c < k; c++) {
        bool free = true;
        for (int w : g[v]) {
            if (color[static_cast<std::size_t>(w)] == c) free = false;
        }
        if (!free) continue;
        color[v] = c;
        if (color_search(g, v + 1, k, color)) return true;
        color[v] = -1;
    }
    return false;
}

inline std::optional<std::vector<int>> find_coloring(const Graph& g, int k) {
    std::vector<int> color(g.size(), -1);
    if (color_search(g, 0, k, color)) return color;
    return std::nullopt;
}