import collections


def topological_sort(edges):
    
    """
    edges: {<node>: [<target-node>, ...]}
    
    Returns a list of node IDs in (a) topological order.
    """
    
    MARK_UNVISITED = 0
    MARK_TEMPORARY = 1  # Visited (but not all children visited yet)
    MARK_PERMANENT = 2  # Node and all its reachable children visited 

    status = {}   
    for src in edges.keys():
        status[src] = MARK_UNVISITED
        
    L = collections.deque()
    stack = []        
        
    # Push the Genesis block
    stack.append(0)    
    
    # Uses nice trick from http://sergebg.blogspot.nl/2014/11/non-recursive-dfs-topological-sort.html
    while True:
        
        try:            
            n = stack.pop()
                    
            if n >= 0:
                # First time we visit this node
                
                st = status[n]
                
                if st == MARK_PERMANENT:
                    continue
                    
                if st == MARK_TEMPORARY:
                    print(edges[n])
                    raise ValueError('Not a DAG (%d is marked as temporary)' % n)     

                status[n] = MARK_TEMPORARY                    
                
                # Push the current node again, but as a negative value so
                # we know with the corresponding pop later that all children have
                # been visited.
                stack.append(-n-1)
                
                # For all edges from n -> m, push a visit to m
                stack.extend(edges[n])
                
            else:
                # Second time for this node, all its children have been visited
                n = -n-1
                assert status[n] == MARK_TEMPORARY
                status[n] = MARK_PERMANENT
                
                L.appendleft(n)
                
        except IndexError:
            # Stack emtpy, all done!
            break
                        
    # Check that we visited all nodes (which must be true as 
    # everything should be reachable from the genesis block)
    for n in status:
        if status[n] != MARK_PERMANENT:
            print('%d: status %d' % (n, status[n]))
        
    return list(L)