Order of Monkeys

In this problem, you are given (n) monkeys numbered from 1 to (n). Each monkey has a learning time provided in a list, though this value is not used in determining the order. The key challenge is that there are precedence constraints given as dependencies: for each dependency ((u, v)), monkey (u) must learn its trick before monkey (v) can start learning. Your task is to determine an ordering of the monkeys such that all dependency constraints are satisfied. This is essentially a topological sort problem on a directed acyclic graph (DAG).

Note: It is guaranteed that the dependency graph will not contain cycles, so a valid ordering always exists.

Hint: You can use Kahn’s algorithm for topological sorting. The algorithm works by repeatedly removing nodes that have no incoming edges and updating the indegree of the neighboring nodes. The constraints can be formally expressed as: if there is a dependency (u \to v), then in the final ordering (position(u) < position(v)).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains a single integer \(n\) representing the number of monkeys.
2. The second line contains \(n\) space-separated integers representing the learning time of each monkey. (This data is provided but is not used in determining the order.)
3. The third line contains a single integer \(m\) representing the number of dependency constraints.
4. The next \(m\) lines each contain two space-separated integers \(u\) and \(v\), indicating that monkey \(u\) must finish learning before monkey \(v\) can begin.

outputFormat

Output a valid ordering of the monkeys as a sequence of \(n\) space-separated integers on a single line to standard output (stdout). If there are multiple valid orderings, any one of them is acceptable.

4
1 2 3 4
2
1 2
3 4

1 3 2 4