from kata_193 import topological_order

def dependency_counts(adj):
    order = topological_order(adj)
    if len(order) != len(adj):
        raise ValueError('graph must be acyclic')
    downstream = [set() for _ in adj]
    for u in reversed(order):
        for v in adj[u]:
            downstream[u].add(v)
            downstream[u].update(downstream[v])
    return [len(nodes) for nodes in downstream]