The order modules run in

traversal dependency order stack recursion compilers

A page loads one JavaScript module, and it pulls in the rest. By the ECMAScript specification a module runs after the modules it imports, and they run in the order in which its import lines are written. Each module runs once. If modules import each other in a loop, the browser does not wait for a module it has already started to run, and goes on.

More precisely, the browser does this. To run module a, it marks it as started, then for each import b in order: if b has not been started, it runs b the same way, and if it has, it skips it. When the imports are over, it runs the code of a itself. Print the modules in the order their code runs. One of the tests is this site's modules: what the browser runs if the page loads the symbolic maths engine.

Input

The first line holds the number n of modules (1 ≤ n ≤ 100,000). Then n lines, one per module: the name, the number k of its imports and k names in the order of the import lines in the file. Names are strings of up to 60 characters without spaces; every module mentioned is described by its own line; there are at most 200,000 imports in all. The last line holds the name of the module the page loads.

Output

The names of the modules that run, in the order they run, one per line.

Examples

Example 1

Input

7
solve.js 6 rational.js ast.js print.js simplify.js expand.js poly.js
poly.js 4 rational.js ast.js expand.js print.js
expand.js 4 rational.js ast.js simplify.js poly.js
simplify.js 2 rational.js ast.js
print.js 2 rational.js ast.js
ast.js 1 rational.js
rational.js 0
solve.js

Output

rational.js
ast.js
print.js
simplify.js
poly.js
expand.js
solve.js

Example 2

Input

5
main 3 a b a
a 1 c
b 2 c main
c 1 a
lonely 1 main
main

Output

c
a
b
main

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Reread the browser's rule and compare it with depth-first traversal. When exactly does a module's code run: on entering it or on leaving?

2Hint 2

A recursive solution takes six lines. How many levels of recursion will the test need where a hundred thousand modules are lined up in a chain?

3Hint 3

If instead of recursion you push all of a module's imports onto the stack at once, the modules come out in the wrong order. What must the stack hold for it to repeat the recursion step by step?

4The idea

The browser's rule is depth-first search from the page's module, where neighbours are gone through in the order of the import lines, and a module is printed at the moment of leaving it: post-order. “Started” is the grey or black colour, so a circular import into a grey module is simply skipped, as in the specification.

5Walkthrough

Recursion is moved onto a stack of one's own like this: the stack holds pairs “module, index of the next import”. At each step look at the top pair. If the imports are over, print the module and pop the pair. Otherwise advance the index and, if the next import has not been started, mark it and push the pair “import, 0”. This is exactly what recursion does: a pair is a frame of the call stack with the line it stopped at.

Why a stack of modules will not do. The loop “pop a module, push all its imports, mark them” visits the same modules, but an import that has lain on the stack for a long time can be popped later than the modules that import it. In the first sample expand.js would then run before poly.js, and in this site's maths engine, when index.js is loaded, the module simplify.js would run before evaluate.js, which it imports. This is wrong.py; the article has a scene showing all such violations.

In the sample with a loop, c runs first, although it imports a, and a has not run yet: the browser reached c from a and did not wait. That is why with circular imports one of the modules always sees another half-finished.

5+Solution

6Complexity

Each module is pushed once, each import is looked at once: O(n + m), where m is the number of imports. Plus the dictionary of names.

7Common mistakes

A stack of modules instead of a stack of frames. The order comes out wrong: wrong.py, which fails on the first sample.
Printing on entry. That is the order in which the browser starts modules, not the order it runs them.
Marking only on exit. Then a circular import leads into endless recursion: a module that has already been started must be skipped at once.
Recursion depth. On a chain of a hundred thousand modules a recursive Python solution without sys.setrecursionlimit crashes with RecursionError.
Sorting the imports. The order of the import lines matters: the answer depends on it.

Algorithms behind it

GRA Algorithm Depth-first search Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E). O(V + E) 2 problems