// A — three-colour directed cycle detection.
static final int WHITE = 0, GREY = 1, BLACK = 2;

boolean hasCycle(List<Integer>[] adj, int u, int[] color) {
    color[u] = GREY;
    for (int v : adj[u]) {
        if (color[v] == GREY) return true;                     // back edge
        if (color[v] == WHITE && hasCycle(adj, v, color)) return true;
    }
    color[u] = BLACK;                                          // finished, and safe
    return false;
}

// B — Kahn. A short order is a cycle report; no separate detection needed.
int[] topo(int n, List<Integer>[] adj) {
    int[] indeg = new int[n];
    for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
    Deque<Integer> q = new ArrayDeque<>();
    for (int u = 0; u < n; u++) if (indeg[u] == 0) q.add(u);
    int[] order = new int[n];
    int k = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        order[k++] = u;
        for (int v : adj[u]) if (--indeg[v] == 0) q.add(v);
    }
    return k == n ? order : new int[0];                        // empty ⇒ cycle
}

// E — DSU. Union by size + path compression. Both, or it is not near-constant.
final class DSU {
    private final int[] parent, size;
    int components;

    DSU(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                            // already together
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        components--;
        return true;
    }

    int sizeOf(int x) { return size[find(x)]; }
}

// H — Kruskal. Sort, union, stop at n-1 accepted edges.
long kruskal(int n, int[][] edges) {          // edges[i] = {u, v, w}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    DSU dsu = new DSU(n);
    long total = 0;
    int used = 0;
    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) { total += e[2]; if (++used == n - 1) break; }
    }
    return used == n - 1 ? total : -1;                         // -1 ⇒ disconnected
}

// H — Prim, O(n^2), no heap. Correct choice when the graph is complete.
long prim(int[][] pts) {
    int n = pts.length;
    int[] best = new int[n];
    boolean[] in = new boolean[n];
    Arrays.fill(best, Integer.MAX_VALUE);
    best[0] = 0;
    long total = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int v = 0; v < n; v++) if (!in[v] && (u == -1 || best[v] < best[u])) u = v;
        in[u] = true;
        total += best[u];
        for (int v = 0; v < n; v++)
            if (!in[v]) best[v] = Math.min(best[v], cost(pts, u, v));
    }
    return total;
}

// I — Tarjan bridges. disc = discovery time, low = highest ancestor reachable.
int timer = 0;

void bridges(int u, int parent, List<Integer>[] adj,
             int[] disc, int[] low, List<List<Integer>> out) {
    disc[u] = low[u] = ++timer;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (disc[v] == 0) {
            bridges(v, u, adj, disc, low, out);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] > disc[u]) out.add(List.of(u, v));      // nothing below v climbs past u
        } else {
            low[u] = Math.min(low[u], disc[v]);                // disc[v], not low[v]
        }
    }
}

// K — Hierholzer. Append on the way OUT, then reverse.
void euler(String u, Map<String, PriorityQueue<String>> adj, LinkedList<String> route) {
    PriorityQueue<String> next = adj.get(u);
    while (next != null && !next.isEmpty()) euler(next.poll(), adj, route);
    route.addFirst(u);                                          // post-order insert
}