// Agrupar con máxima separación: ocho puntos en el plano. El peso de cada arista es la
// distancia al cuadrado, un entero, que ordena igual que la distancia.
#include <iostream>
#include <string>
#include <vector>

#include "digraph.h"
#include "mst.h"

namespace {

struct Point {
    int x;
    int y;
};

std::vector<Edge> complete_graph(const std::vector<Point>& points) {
    std::vector<Edge> edges;
    int n = static_cast<int>(points.size());
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dx = points[i].x - points[j].x;
            int dy = points[i].y - points[j].y;
            edges.push_back({i, j, dx * dx + dy * dy});
        }
    }
    return edges;
}

}  // namespace

int main() {
    std::vector<Point> points = {{0, 0}, {0, 2}, {2, 1}, {10, 0}, {11, 2}, {12, 0}, {5, 9}, {6, 10}};
    int n = static_cast<int>(points.size());
    std::vector<Edge> edges = complete_graph(points);

    std::cout << "Puntos:";
    for (int i = 0; i < n; i++) {
        std::cout << " " << i << "=(" << points[i].x << "," << points[i].y << ")";
    }
    std::cout << "\n\nÁrbol de expansión mínima, de la arista más barata a la más cara:\n ";
    for (const Edge& e : sorted_by_weight(kruskal(n, edges))) {
        std::cout << " " << e.u << "-" << e.v << ":" << e.weight;
    }
    std::cout << "\n\n";

    for (int k = 2; k <= 4; k++) {
        std::vector<int> group = max_spacing_groups(n, edges, k);
        long long partitions = 0;
        int best = best_spacing_brute(n, edges, k, &partitions);
        std::cout << "k = " << k << ": " << groups_text(group) << "\n";
        std::cout << "  separación " << spacing(edges, group) << ", fuerza bruta " << best << " entre " << partitions
                  << " particiones\n";
    }

    std::vector<Edge> sorted = sorted_by_weight(edges);
    sorted.resize(sorted.size() - 2);
    std::cout << "\nIdea que falla, k = 3: quitar las 2 aristas más caras del grafo completo\n";
    std::cout << "  quedan " << count_components(n, sorted) << " grupo\n";
}

// DFS sobre un camino de n nodos, primero con pila explícita y luego con recursión.
//   build/deep_recursion n
#include <cstdlib>
#include <iostream>
#include <vector>

#include "digraph.h"

namespace {

// noinline: si el compilador la mezcla consigo misma, ya no se mide un marco por nodo.
__attribute__((noinline)) void visit(const Digraph& g, std::vector<bool>& marked, int u, int& finished) {
    marked[u] = true;
    for (int v : g[u]) {
        if (!marked[v]) visit(g, marked, v, finished);
    }
    finished++;
}

}  // namespace

int main(int argc, char** argv) {
    int n = argc > 1 ? std::atoi(argv[1]) : 1000000;
    Digraph path(static_cast<std::size_t>(n));
    for (int i = 0; i + 1 < n; i++) path[i].push_back(i + 1);

    DfsTimes t = dfs_iterative(path);
    std::cout << "con pila explícita: terminaron " << t.finish_order.size() << " nodos" << std::endl;

    std::vector<bool> marked(static_cast<std::size_t>(n), false);
    int finished = 0;
    visit(path, marked, 0, finished);
    std::cout << "con recursión: terminaron " << finished << " nodos" << std::endl;
}

// DFS con tiempos: la tabla de la clase, los tipos de arista, el orden topológico y el atajo.
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

#include "digraph.h"

namespace {

std::string order_text(const std::vector<int>& order) {
    std::string text;
    for (int v : order) text += std::to_string(v) + " ";
    if (!text.empty()) text.pop_back();
    return text;
}

}  // namespace

int main() {
    Digraph g = {{1, 2, 3}, {2}, {0}, {2}, {3, 5}, {4}};
    std::vector<ClassifiedEdge> kinds;
    DfsTimes t = dfs_recursive(g, &kinds);
    std::cout << "Grafo con ciclos:\n";
    std::cout << "  nodo  inicio  fin\n";
    for (int v = 0; v < static_cast<int>(g.size()); v++) {
        std::printf("  %4d  %6d  %3d\n", v, t.start[v], t.finish[v]);
    }
    std::cout << "  arista  tipo\n";
    for (const ClassifiedEdge& e : kinds) {
        std::printf("  %d -> %d  %s\n", e.u, e.v, kind_name(e.kind));
    }

    // Tareas para armar un programa: toda arista va de una tarea a otra que la necesita.
    Digraph dag = {{1, 2}, {3}, {3, 4}, {5}, {5}, {}};
    DfsTimes d = dfs_recursive(dag);
    std::cout << "\nDAG: 0->1 0->2 1->3 2->3 2->4 3->5 4->5\n";
    std::cout << "  nodo  inicio  fin\n";
    for (int v = 0; v < static_cast<int>(dag.size()); v++) {
        std::printf("  %4d  %6d  %3d\n", v, d.start[v], d.finish[v]);
    }
    std::cout << "  terminan en este orden: " << order_text(d.finish_order) << "\n";
    std::vector<int> topo = reverse_finish_order(dag);
    std::cout << "  orden decreciente de fin: " << order_text(topo) << "  "
              << (is_topological(dag, topo) ? "es topológico" : "no es topológico") << "\n";

    Digraph with_cycle = {{1}, {2}, {0, 3}, {}};
    std::vector<int> not_topo = reverse_finish_order(with_cycle);
    std::cout << "\nCon un ciclo: 0->1 1->2 2->0 2->3\n";
    std::cout << "  orden decreciente de fin: " << order_text(not_topo) << "  "
              << (is_topological(with_cycle, not_topo) ? "es topológico" : "no es topológico") << "\n";

    Digraph small = {{1, 2}, {2}, {}};
    std::vector<int> shortcut = stack_shortcut_order(small);
    std::vector<int> shortcut_reversed(shortcut.rbegin(), shortcut.rend());
    DfsTimes real = dfs_iterative(small);
    std::cout << "\nEl atajo de la pila, en 0->1 0->2 1->2:\n";
    std::cout << "  pila con (nodo, siguiente), terminan: " << order_text(real.finish_order)
              << "  al revés: " << order_text(reverse_finish_order(small)) << "  "
              << (is_topological(small, reverse_finish_order(small)) ? "topológico" : "no topológico") << "\n";
    std::cout << "  atajo, orden al sacar: " << order_text(shortcut) << "  "
              << (is_topological(small, shortcut) ? "topológico" : "no topológico") << "\n";
    std::cout << "  atajo, al revés:       " << order_text(shortcut_reversed) << "  "
              << (is_topological(small, shortcut_reversed) ? "topológico" : "no topológico") << "\n";
}

// 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;
}

// Kruskal contra Prim con grafos al azar conexos, compilado con -O2. Toma el menor de 3 intentos.
// Las entradas y descartes de la cola no dependen de la máquina; los tiempos sí.
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

#include "mst.h"

namespace {

std::vector<Edge> random_connected(int n, int m, unsigned seed) {
    std::mt19937 rng(seed);
    std::vector<Edge> edges;
    edges.reserve(static_cast<std::size_t>(m));
    for (int v = 1; v < n; v++) {
        edges.push_back({static_cast<int>(rng() % static_cast<unsigned>(v)), v, static_cast<int>(rng() % 1000000000U)});
    }
    while (static_cast<int>(edges.size()) < m) {
        int a = static_cast<int>(rng() % static_cast<unsigned>(n));
        int b = static_cast<int>(rng() % static_cast<unsigned>(n));
        if (a != b) edges.push_back({a, b, static_cast<int>(rng() % 1000000000U)});
    }
    return edges;
}

template <typename Run>
double best_ms(Run run) {
    double best = 1e18;
    for (int attempt = 0; attempt < 3; attempt++) {
        auto begin = std::chrono::steady_clock::now();
        run();
        auto end = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(end - begin).count());
    }
    return best;
}

}  // namespace

int main() {
    std::printf("%8s %9s %11s %9s %11s %10s %10s\n", "V", "E", "kruskal ms", "prim ms", "entradas", "descartes", "costo igual");
    for (auto [n, m] : std::vector<std::pair<int, int>>{{50000, 200000}, {200000, 800000}, {800000, 3200000},
                                                        {100000, 3200000}, {3000, 3200000}}) {
        std::vector<Edge> edges = random_connected(n, m, 2026);
        long long kruskal_cost = 0;
        long long prim_cost = 0;
        long long pushes = 0;
        long long stale = 0;
        double k_ms = best_ms([&] { kruskal_cost = total_weight(kruskal(n, edges)); });
        double p_ms = best_ms([&] {
            PrimResult result = prim(n, edges, 0);
            prim_cost = total_weight(result.tree);
            pushes = result.pushes;
            stale = result.stale_pops;
        });
        std::printf("%8d %9d %11.1f %9.1f %11lld %10lld %10s\n", n, m, k_ms, p_ms, pushes, stale,
                    kruskal_cost == prim_cost ? "sí" : "NO");
    }
}

// El grafo de la clase: Kruskal y Prim paso a paso, y las ideas parecidas que fallan.
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

#include "mst.h"

namespace {

const int kNodes = 7;

std::vector<Edge> class_graph() {
    return {{0, 1, 7}, {0, 3, 5}, {1, 2, 8}, {1, 3, 9}, {1, 4, 6}, {2, 4, 4},
            {3, 4, 15}, {3, 5, 10}, {4, 5, 12}, {4, 6, 11}, {5, 6, 13}};
}

std::string edges_text(const std::vector<Edge>& edges) {
    std::string text;
    for (const Edge& e : edges) {
        text += std::to_string(e.u) + "-" + std::to_string(e.v) + ":" + std::to_string(e.weight) + " ";
    }
    if (!text.empty()) text.pop_back();
    return text;
}

void kruskal_trace(const std::vector<Edge>& edges) {
    std::cout << "Kruskal:\n";
    std::cout << "  arista  peso  se toma  grupos después\n";
    UnionFind sets(kNodes);
    std::vector<Edge> so_far;
    for (const Edge& e : sorted_by_weight(edges)) {
        bool taken = sets.unite(e.u, e.v);
        if (taken) so_far.push_back(e);
        std::printf("  %d-%d %7d  %s      %d\n", e.u, e.v, e.weight, taken ? "sí" : "no", sets.sets());
    }
    std::cout << "  costo " << total_weight(so_far) << ", " << so_far.size() << " aristas\n";
}

void prim_trace(const std::vector<Edge>& edges) {
    std::cout << "\nPrim desde 0 (arista que sale de la cola, y qué pasa):\n";
    using Entry = std::tuple<int, int, int>;
    auto adj = adjacency(kNodes, edges);
    std::vector<bool> in_tree(kNodes, false);
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    long long pushes = 0;
    long long stale = 0;
    long long cost = 0;
    auto add_node = [&](int u) {
        in_tree[u] = true;
        for (const Neighbor& nb : adj[u]) {
            if (!in_tree[nb.to]) {
                heap.push({nb.weight, nb.to, u});
                pushes++;
            }
        }
    };
    add_node(0);
    while (!heap.empty()) {
        auto [weight, v, from] = heap.top();
        heap.pop();
        if (in_tree[v]) {
            stale++;
            std::printf("  %d-%d:%-3d descartada: %d ya está en el árbol\n", from, v, weight, v);
            continue;
        }
        add_node(v);
        cost += weight;
        std::printf("  %d-%d:%-3d entra %d, quedan %zu en la cola\n", from, v, weight, v, heap.size());
    }
    std::cout << "  costo " << cost << ", entradas " << pushes << ", descartadas " << stale << ", aristas del grafo "
              << edges.size() << "\n";
}

void show_idea(const std::string& name, const std::vector<Edge>& chosen) {
    std::cout << name << "\n";
    std::cout << "  aristas: " << edges_text(chosen) << "\n";
    std::cout << "  costo " << total_weight(chosen) << ", grupos " << count_components(kNodes, chosen) << ", "
              << (is_spanning_tree(kNodes, chosen) ? "es árbol de expansión" : "no es árbol de expansión") << "\n";
}

}  // namespace

int main() {
    std::vector<Edge> edges = class_graph();
    kruskal_trace(edges);
    prim_trace(edges);

    auto spanning = all_spanning_trees(kNodes, edges);
    auto minimum = all_minimum_trees(kNodes, edges);
    long long best = 0;
    for (int c : minimum[0]) best += edges[c].weight;
    std::cout << "\nFuerza bruta: " << spanning.size() << " árboles de expansión, mínimo " << best << ", "
              << minimum.size() << " de ese costo\n\n";

    show_idea("Las n - 1 aristas más baratas:", cheapest_edges_only(kNodes, edges));
    show_idea("Cada nodo elige su arista más barata:", cheapest_per_node(kNodes, edges));
    show_idea("Árbol de caminos mínimos desde 0:", dijkstra(kNodes, edges, 0).tree);
}

// Un árbol de expansión mínima no contiene los caminos mínimos, y sumar una constante
// afecta a un problema y no al otro.
#include <iostream>
#include <string>
#include <vector>

#include "mst.h"

namespace {

std::string edges_text(const std::vector<Edge>& edges) {
    std::string text;
    for (const Edge& e : edges) {
        text += std::to_string(e.u) + "-" + std::to_string(e.v) + ":" + std::to_string(e.weight) + " ";
    }
    if (!text.empty()) text.pop_back();
    return text;
}

long long distance(int n, const std::vector<Edge>& edges, int from, int to) {
    return dijkstra(n, edges, from).dist[to];
}

std::vector<Edge> add_constant(std::vector<Edge> edges, int c) {
    for (Edge& e : edges) e.weight += c;
    return edges;
}

}  // namespace

int main() {
    std::vector<Edge> triangle = {{0, 1, 2}, {1, 2, 2}, {0, 2, 3}};
    std::vector<Edge> mst = kruskal(3, triangle);
    std::vector<Edge> paths = dijkstra(3, triangle, 0).tree;
    std::cout << "Triángulo: 0-1:2 1-2:2 0-2:3\n";
    std::cout << "  árbol de expansión mínima: " << edges_text(mst) << " costo " << total_weight(mst) << "\n";
    std::cout << "  de 0 a 2 dentro de ese árbol: " << distance(3, mst, 0, 2) << "\n";
    std::cout << "  de 0 a 2 en el grafo:         " << distance(3, triangle, 0, 2) << "\n";
    std::cout << "  árbol de caminos desde 0:  " << edges_text(paths) << " costo " << total_weight(paths) << "\n";

    std::vector<Edge> square = {{0, 1, 1}, {1, 2, 1}, {0, 2, 3}, {2, 3, 2}, {1, 3, 4}};
    std::cout << "\nSumar una constante c a todas las aristas de 0-1:1 1-2:1 0-2:3 2-3:2 1-3:4\n";
    std::cout << " c  árbol de expansión mínima    costo  distancia 0 a 2  camino\n";
    for (int c : {0, 1, 2, 10}) {
        std::vector<Edge> shifted = add_constant(square, c);
        std::vector<Edge> tree = kruskal(4, shifted);
        long long direct = shifted[2].weight;
        long long by_one = shifted[0].weight + shifted[1].weight;
        long long d = distance(4, shifted, 0, 2);
        std::string route = direct < by_one ? "0-2" : (by_one < direct ? "0-1-2" : "empate");
        std::string kept;
        for (const Edge& e : tree) kept += std::to_string(e.u) + "-" + std::to_string(e.v) + " ";
        std::cout << (c < 10 ? " " : "") << c << "  " << kept << std::string(29 - kept.size(), ' ')
                  << total_weight(tree) << (total_weight(tree) < 10 ? "      " : "     ") << d
                  << (d < 10 ? "                " : "               ") << route << "\n";
    }
}

// Árboles de expansión mínima: Kruskal, Prim, agrupamiento y las ideas que fallan.
#pragma once

#include <algorithm>
#include <cstddef>
#include <functional>
#include <limits>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

struct Edge {
    int u;
    int v;
    int weight;
};

inline long long total_weight(const std::vector<Edge>& edges) {
    long long total = 0;
    for (const Edge& e : edges) total += e.weight;
    return total;
}

class UnionFind {
public:
    explicit UnionFind(int n) : parent_(static_cast<std::size_t>(n)), size_(static_cast<std::size_t>(n), 1), sets_(n) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }

    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];  // compresión por mitades
            x = parent_[x];
        }
        return x;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (size_[a] < size_[b]) std::swap(a, b);
        parent_[b] = a;
        size_[a] += size_[b];
        sets_--;
        return true;
    }

    int sets() const { return sets_; }

private:
    std::vector<int> parent_;
    std::vector<int> size_;
    int sets_;
};

// Ordena por peso. Con pesos iguales respeta el orden de la lista.
inline std::vector<Edge> sorted_by_weight(std::vector<Edge> edges) {
    std::stable_sort(edges.begin(), edges.end(),
                     [](const Edge& a, const Edge& b) { return a.weight < b.weight; });
    return edges;
}

// Devuelve un bosque de expansión mínima: un árbol por cada componente del grafo.
// Si el grafo es conexo, tiene n - 1 aristas.
inline std::vector<Edge> kruskal(int n, const std::vector<Edge>& edges) {
    UnionFind sets(n);
    std::vector<Edge> forest;
    for (const Edge& e : sorted_by_weight(edges)) {
        // Invariante: forest está contenido en algún árbol de expansión mínima.
        if (sets.unite(e.u, e.v)) forest.push_back(e);
    }
    return forest;
}

struct Neighbor {
    int to;
    int weight;
};

inline std::vector<std::vector<Neighbor>> adjacency(int n, const std::vector<Edge>& edges) {
    std::vector<std::vector<Neighbor>> adj(static_cast<std::size_t>(n));
    for (const Edge& e : edges) {
        adj[e.u].push_back({e.v, e.weight});
        adj[e.v].push_back({e.u, e.weight});
    }
    return adj;
}

struct PrimResult {
    std::vector<Edge> tree;
    long long pushes = 0;      // entradas que entraron a la cola
    long long stale_pops = 0;  // entradas que salieron y se descartaron
};

// Crece desde source. std::priority_queue no puede bajar la clave de una entrada, así que se
// usa borrado perezoso: las entradas viejas se quedan y se descartan cuando salen.
inline PrimResult prim(int n, const std::vector<Edge>& edges, int source) {
    using Entry = std::tuple<int, int, int>;  // peso, nodo de afuera, nodo del árbol
    auto adj = adjacency(n, edges);
    std::vector<bool> in_tree(static_cast<std::size_t>(n), false);
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    PrimResult result;

    auto add_node = [&](int u) {
        in_tree[u] = true;
        for (const Neighbor& nb : adj[u]) {
            if (!in_tree[nb.to]) {
                heap.push({nb.weight, nb.to, u});
                result.pushes++;
            }
        }
    };

    add_node(source);
    while (!heap.empty()) {
        auto [weight, v, from] = heap.top();
        heap.pop();
        if (in_tree[v]) {
            result.stale_pops++;  // sus dos extremos ya están adentro: no cruza el corte
            continue;
        }
        result.tree.push_back({from, v, weight});
        add_node(v);
    }
    return result;
}

// Distancias desde source con Dijkstra. También devuelve la arista con que se fijó cada nodo.
struct DijkstraResult {
    std::vector<long long> dist;
    std::vector<Edge> tree;
};

inline DijkstraResult dijkstra(int n, const std::vector<Edge>& edges, int source) {
    using Entry = std::tuple<long long, int, int, int>;  // distancia, nodo de afuera, nodo del árbol, peso
    auto adj = adjacency(n, edges);
    std::vector<bool> in_tree(static_cast<std::size_t>(n), false);
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
    DijkstraResult result;
    result.dist.assign(static_cast<std::size_t>(n), -1);

    auto add_node = [&](int u, long long du) {
        in_tree[u] = true;
        result.dist[u] = du;
        for (const Neighbor& nb : adj[u]) {
            if (!in_tree[nb.to]) heap.push({du + nb.weight, nb.to, u, nb.weight});
        }
    };

    add_node(source, 0);
    while (!heap.empty()) {
        auto [d, v, from, weight] = heap.top();
        heap.pop();
        if (in_tree[v]) continue;
        result.tree.push_back({from, v, weight});
        add_node(v, d);
    }
    return result;
}

// Idea que falla: las n - 1 aristas más baratas, sin mirar si forman ciclos.
inline std::vector<Edge> cheapest_edges_only(int n, const std::vector<Edge>& edges) {
    std::vector<Edge> sorted = sorted_by_weight(edges);
    std::size_t count = std::min(sorted.size(), static_cast<std::size_t>(n - 1));
    sorted.resize(count);
    return sorted;
}

// Idea que falla: cada nodo se queda con su arista más barata.
inline std::vector<Edge> cheapest_per_node(int n, const std::vector<Edge>& edges) {
    std::vector<int> best(static_cast<std::size_t>(n), -1);
    for (int i = 0; i < static_cast<int>(edges.size()); i++) {
        for (int end : {edges[i].u, edges[i].v}) {
            if (best[end] == -1 || edges[i].weight < edges[best[end]].weight) best[end] = i;
        }
    }
    std::vector<int> chosen;
    for (int i : best) {
        if (i != -1) chosen.push_back(i);
    }
    std::sort(chosen.begin(), chosen.end());
    chosen.erase(std::unique(chosen.begin(), chosen.end()), chosen.end());
    std::vector<Edge> result;
    for (int i : chosen) result.push_back(edges[i]);
    return result;
}

inline int count_components(int n, const std::vector<Edge>& edges) {
    UnionFind sets(n);
    for (const Edge& e : edges) sets.unite(e.u, e.v);
    return sets.sets();
}

// Un árbol de expansión de n nodos: n - 1 aristas que conectan todo.
inline bool is_spanning_tree(int n, const std::vector<Edge>& edges) {
    return static_cast<int>(edges.size()) == n - 1 && count_components(n, edges) == 1;
}

// Fuerza bruta: todos los árboles de expansión. Solo para grafos pequeños.
inline std::vector<std::vector<int>> all_spanning_trees(int n, const std::vector<Edge>& edges) {
    std::vector<std::vector<int>> trees;
    std::vector<int> chosen;
    std::function<void(int)> go = [&](int i) {
        if (static_cast<int>(chosen.size()) == n - 1) {
            std::vector<Edge> picked;
            for (int c : chosen) picked.push_back(edges[c]);
            if (count_components(n, picked) == 1) trees.push_back(chosen);
            return;
        }
        if (i == static_cast<int>(edges.size())) return;
        chosen.push_back(i);
        go(i + 1);
        chosen.pop_back();
        go(i + 1);
    };
    go(0);
    return trees;
}

// Fuerza bruta: los árboles de expansión de costo mínimo, como listas de índices de aristas.
inline std::vector<std::vector<int>> all_minimum_trees(int n, const std::vector<Edge>& edges) {
    std::vector<std::vector<int>> best;
    long long best_cost = std::numeric_limits<long long>::max();
    for (const std::vector<int>& tree : all_spanning_trees(n, edges)) {
        long long cost = 0;
        for (int c : tree) cost += edges[c].weight;
        if (cost < best_cost) {
            best_cost = cost;
            best.clear();
        }
        if (cost == best_cost) best.push_back(tree);
    }
    return best;
}

// Grupos de una lista de aristas: group[v] es el número del grupo de v, por orden de aparición.
inline std::vector<int> groups_of(int n, const std::vector<Edge>& edges) {
    UnionFind sets(n);
    for (const Edge& e : edges) sets.unite(e.u, e.v);
    std::vector<int> label(static_cast<std::size_t>(n), -1);
    std::vector<int> group(static_cast<std::size_t>(n));
    int next = 0;
    for (int v = 0; v < n; v++) {
        int root = sets.find(v);
        if (label[root] == -1) label[root] = next++;
        group[v] = label[root];
    }
    return group;
}

// Agrupar en k grupos: quitar las k - 1 aristas más caras de un árbol de expansión mínima.
inline std::vector<int> max_spacing_groups(int n, const std::vector<Edge>& edges, int k) {
    std::vector<Edge> kept = sorted_by_weight(kruskal(n, edges));
    kept.resize(kept.size() - static_cast<std::size_t>(k - 1));
    return groups_of(n, kept);
}

// Separación: la arista más barata entre dos grupos distintos. -1 si ninguna los une.
inline int spacing(const std::vector<Edge>& edges, const std::vector<int>& group) {
    int best = -1;
    for (const Edge& e : edges) {
        if (group[e.u] != group[e.v] && (best == -1 || e.weight < best)) best = e.weight;
    }
    return best;
}

// Fuerza bruta: la mayor separación entre todas las particiones en k grupos no vacíos.
// partitions, si no es nulo, recibe cuántas particiones se probaron.
inline int best_spacing_brute(int n, const std::vector<Edge>& edges, int k, long long* partitions = nullptr) {
    std::vector<int> group(static_cast<std::size_t>(n), 0);
    int best = -1;
    long long seen = 0;
    // Cada partición se genera una vez: el grupo de v es a lo sumo uno más que los ya usados.
    std::function<void(int, int)> go = [&](int v, int used) {
        if (v == n) {
            if (used == k) {
                seen++;
                best = std::max(best, spacing(edges, group));
            }
            return;
        }
        for (int g = 0; g <= used && g < k; g++) {
            group[v] = g;
            go(v + 1, std::max(used, g + 1));
        }
    };
    go(0, 0);
    if (partitions != nullptr) *partitions = seen;
    return best;
}