Problem G
Build Dependencies
Input
The input consists of:
-
one line with one integer $n$ ($1\leq n \leq 100\, 000$), the number of Makefile rules;
-
$n$ lines, each with a Makefile rule. Such a rule starts with “$f$:” where $f$ is a filename, and is then followed by a list of the filenames of the dependencies of $f$. Each file has at most $5$ dependencies.
-
one line with one string $c$, the filename of the changed file.
Filenames are strings consisting of between $1$ and $10$ lowercase letters. Exactly $n$ different filenames appear in the input file, each appearing exactly once as $f$ in a Makefile rule. The rules are such that no two files depend (directly or indirectly) on each other.
Output
Output the set of files that need to be recompiled, in an order such that all dependencies are satisfied. If there are multiple valid answers you may output any of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 gmp: solution: set map queue base: set: base gmp map: base gmp queue: base gmp |
gmp map set solution |
