#!/usr/bin/python
"""Topological multi-sort.

Each line of input is either a #comment or a start-node-name and a
list of end-node-names.

Output is a topological sort of non-comment lines.

Specifically, lines with X as a start-node-name must come before any
lines with X as an end-node-name.

"""
import sys
import fileinput

def main(argv):
    comments = []
    nodes = {}
    for line in fileinput.input():
        if line.startswith('#'):
            comments.append(line)
            continue

        words = line.split()
        node = words[0]
        if node not in nodes:
            nodes[node] = ([], [])
        nn = nodes[node]
        nn[0].extend(words[1:])
        nn[1].extend(comments)
        comments = []
        nn[1].append(line)

    already_output = set()
    while len(already_output) < len(nodes):
        free_nodes = [nn for nn, (endnames, lines) in nodes.items()
                      if nn not in already_output
                      and all(en in already_output
                              or en not in nodes
                              for en in endnames)]

        if not free_nodes:
            sys.stderr.write("circular dependency %r\n" % (nodes,))
            return 1
        for nn in free_nodes:
            _, lines = nodes[nn]
            for line in lines:
                sys.stdout.write(line)
            already_output.add(nn)

if __name__ == '__main__':
    sys.exit(main(sys.argv))