"""Deterministic topological sort (Kahn's algorithm) with cycle detection.

Nodes are arbitrary hashable values. Input is an iterable of (node, predecessors)
pairs where predecessors are the nodes that must come before node. Ordering
among independent nodes is stable by input order of first appearance (earliest
discovered zero-indegree / ready node wins).

Returns a list of nodes in topological order. Raises CycleError if the graph
contains a cycle, listing the remaining (unsorted) nodes.
"""
from __future__ import annotations

import heapq
from collections import OrderedDict


class CycleError(Exception):
    def __init__(self, remaining):
        self.remaining = tuple(remaining)
        super().__init__("cycle detected among: %r" % (self.remaining,))


def topo_sort(edges):
    order = OrderedDict()   # node -> discovery index
    preds = {}
    succs = {}
    indeg = {}

    idx = 0
    def discover(n):
        nonlocal idx
        if n not in order:
            order[n] = idx
            idx += 1
            preds[n] = set()
            succs[n] = []
            indeg[n] = 0

    for node, predecessors in edges:
        discover(node)
        for p in predecessors:
            discover(p)
            if p not in preds[node]:
                preds[node].add(p)
                succs[p].append(node)
                indeg[node] += 1

    # Kahn with a min-heap keyed by discovery index for global stability.
    heap = [(order[n], n) for n in order if indeg[n] == 0]
    heapq.heapify(heap)
    result = []
    while heap:
        _, n = heapq.heappop(heap)
        result.append(n)
        for s in succs[n]:
            indeg[s] -= 1
            if indeg[s] == 0:
                heapq.heappush(heap, (order[s], s))

    if len(result) != len(order):
        remaining = [n for n in order if n not in set(result)]
        raise CycleError(remaining)
    return result


def has_cycle(edges):
    try:
        topo_sort(edges)
        return False
    except CycleError:
        return True