// Grafos dirigidos: DFS con tiempos, tipos de arista, orden topológico y componentes
// fuertemente conexas. Un grafo es una lista de adyacencia con nodos de 0 a n - 1.
#pragma once

#include <algorithm>
#include <cstddef>
#include <functional>
#include <string>
#include <utility>
#include <vector>

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

inline Digraph make_digraph(int n, const std::vector<std::pair<int, int>>& arcs) {
    Digraph g(static_cast<std::size_t>(n));
    for (auto [u, v] : arcs) g[u].push_back(v);
    return g;
}

inline Digraph reversed(const Digraph& g) {
    Digraph r(g.size());
    for (int u = 0; u < static_cast<int>(g.size()); u++) {
        for (int v : g[u]) r[v].push_back(u);
    }
    return r;
}

// Tiempos de un DFS completo. Cada inicio y cada fin avanzan el reloj en 1, desde 1.
struct DfsTimes {
    std::vector<int> start;
    std::vector<int> finish;
    std::vector<int> finish_order;  // los nodos, en el orden en que terminaron
};

enum class EdgeKind { tree, back, forward, cross };

inline const char* kind_name(EdgeKind kind) {
    switch (kind) {
        case EdgeKind::tree: return "árbol";
        case EdgeKind::back: return "atrás";
        case EdgeKind::forward: return "adelante";
        case EdgeKind::cross: return "cruce";
    }
    return "";
}

struct ClassifiedEdge {
    int u;
    int v;
    EdgeKind kind;
};

// Versión recursiva, la que se demuestra. Inicia en los nodos de 0 a n - 1.
inline DfsTimes dfs_recursive(const Digraph& g, std::vector<ClassifiedEdge>* kinds = nullptr) {
    int n = static_cast<int>(g.size());
    DfsTimes t;
    t.start.assign(static_cast<std::size_t>(n), 0);
    t.finish.assign(static_cast<std::size_t>(n), 0);
    int clock = 0;
    std::function<void(int)> visit = [&](int u) {
        t.start[u] = ++clock;
        for (int v : g[u]) {
            if (t.start[v] == 0) {
                if (kinds != nullptr) kinds->push_back({u, v, EdgeKind::tree});
                visit(v);
            } else if (kinds != nullptr) {
                EdgeKind kind = t.finish[v] == 0        ? EdgeKind::back
                                : t.start[u] < t.start[v] ? EdgeKind::forward
                                                          : EdgeKind::cross;
                kinds->push_back({u, v, kind});
            }
        }
        t.finish[u] = ++clock;
        t.finish_order.push_back(u);
    };
    for (int u = 0; u < n; u++) {
        if (t.start[u] == 0) visit(u);
    }
    return t;
}

// Versión con pila explícita. Cada elemento guarda lo mismo que un marco de llamada: el nodo y
// por cuál arista iba. Un nodo termina recién cuando se le acaban las aristas.
inline DfsTimes dfs_iterative(const Digraph& g) {
    int n = static_cast<int>(g.size());
    DfsTimes t;
    t.start.assign(static_cast<std::size_t>(n), 0);
    t.finish.assign(static_cast<std::size_t>(n), 0);
    int clock = 0;
    std::vector<std::pair<int, std::size_t>> stack;
    for (int root = 0; root < n; root++) {
        if (t.start[root] != 0) continue;
        t.start[root] = ++clock;
        stack.push_back({root, 0});
        while (!stack.empty()) {
            auto [u, next] = stack.back();
            if (next == g[u].size()) {
                t.finish[u] = ++clock;
                t.finish_order.push_back(u);
                stack.pop_back();
                continue;
            }
            stack.back().second++;
            int v = g[u][next];
            if (t.start[v] == 0) {
                t.start[v] = ++clock;
                stack.push_back({v, 0});
            }
        }
    }
    return t;
}

// El atajo: meter todos los vecinos en la pila y anotar cada nodo al sacarlo.
// Visita los mismos nodos, pero no sabe cuándo termina nadie.
inline std::vector<int> stack_shortcut_order(const Digraph& g) {
    int n = static_cast<int>(g.size());
    std::vector<bool> marked(static_cast<std::size_t>(n), false);
    std::vector<int> order;
    std::vector<int> stack;
    for (int root = 0; root < n; root++) {
        stack.push_back(root);
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            if (marked[u]) continue;
            marked[u] = true;
            order.push_back(u);
            for (int v : g[u]) {
                if (!marked[v]) stack.push_back(v);
            }
        }
    }
    return order;
}

// Orden topológico: los nodos en orden decreciente de fin. Solo significa algo en un DAG.
inline std::vector<int> reverse_finish_order(const Digraph& g) {
    std::vector<int> order = dfs_iterative(g).finish_order;
    std::reverse(order.begin(), order.end());
    return order;
}

inline bool is_topological(const Digraph& g, const std::vector<int>& order) {
    std::vector<int> position(g.size());
    for (int i = 0; i < static_cast<int>(order.size()); i++) position[order[i]] = i;
    for (int u = 0; u < static_cast<int>(g.size()); u++) {
        for (int v : g[u]) {
            if (position[u] >= position[v]) return false;
        }
    }
    return true;
}

// Recorre desde cada nodo de order todavía sin grupo. comp[v] es el número del recorrido que
// lo alcanzó. Este paso no necesita tiempos: solo qué se alcanza.
inline std::vector<int> label_in_order(const Digraph& g, const std::vector<int>& order) {
    std::vector<int> comp(g.size(), -1);
    int next = 0;
    std::vector<int> stack;
    for (int root : order) {
        if (comp[root] != -1) continue;
        comp[root] = next;
        stack.push_back(root);
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            for (int v : g[u]) {
                if (comp[v] == -1) {
                    comp[v] = next;
                    stack.push_back(v);
                }
            }
        }
        next++;
    }
    return comp;
}

// Kosaraju-Sharir: DFS sobre el grafo invertido para obtener el orden, y recorrido sobre el
// original en orden decreciente de fin. Las componentes salen de sumidero a fuente.
inline std::vector<int> strong_components(const Digraph& g) {
    std::vector<int> order = dfs_iterative(reversed(g)).finish_order;
    std::reverse(order.begin(), order.end());
    return label_in_order(g, order);
}

// El error: sacar el orden del mismo grafo, sin invertirlo.
inline std::vector<int> components_without_reversing(const Digraph& g) {
    return label_in_order(g, reverse_finish_order(g));
}

// Fuerza bruta: la matriz de quién alcanza a quién por un camino de al menos una arista.
inline std::vector<std::vector<bool>> reach_matrix(const Digraph& g) {
    int n = static_cast<int>(g.size());
    std::vector<std::vector<bool>> reach(static_cast<std::size_t>(n), std::vector<bool>(static_cast<std::size_t>(n), false));
    for (int s = 0; s < n; s++) {
        std::vector<int> stack = {s};
        while (!stack.empty()) {
            int u = stack.back();
            stack.pop_back();
            for (int v : g[u]) {
                if (!reach[s][v]) {
                    reach[s][v] = true;
                    stack.push_back(v);
                }
            }
        }
    }
    return reach;
}

// Fuerza bruta: componentes por la definición. u y v van juntos si cada uno alcanza al otro.
inline std::vector<int> components_brute(const Digraph& g) {
    int n = static_cast<int>(g.size());
    auto reach = reach_matrix(g);
    std::vector<int> comp(static_cast<std::size_t>(n), -1);
    int next = 0;
    for (int u = 0; u < n; u++) {
        if (comp[u] != -1) continue;
        comp[u] = next;
        for (int v = u + 1; v < n; v++) {
            if (reach[u][v] && reach[v][u]) comp[v] = next;
        }
        next++;
    }
    return comp;
}

// Dos numeraciones de grupos son la misma partición si van juntos los mismos pares.
inline bool same_partition(const std::vector<int>& a, const std::vector<int>& b) {
    for (std::size_t i = 0; i < a.size(); i++) {
        for (std::size_t j = i + 1; j < a.size(); j++) {
            if ((a[i] == a[j]) != (b[i] == b[j])) return false;
        }
    }
    return true;
}

inline std::string groups_text(const std::vector<int>& comp) {
    int groups = comp.empty() ? 0 : *std::max_element(comp.begin(), comp.end()) + 1;
    std::string text;
    for (int c = 0; c < groups; c++) {
        text += '{';
        bool first = true;
        for (int v = 0; v < static_cast<int>(comp.size()); v++) {
            if (comp[v] != c) continue;
            if (!first) text += ' ';
            text += std::to_string(v);
            first = false;
        }
        text += "} ";
    }
    if (!text.empty()) text.pop_back();
    return text;
}