Task Scheduling with Dependencies

You are given a list of tasks and a list of dependency pairs. Each dependency is given as a pair (u, v) which indicates that task u must be completed before task v can start. Your goal is to determine a valid order in which tasks can be executed such that all dependencies are met.

If there exists a valid ordering, print the tasks in order separated by a space. If no valid ordering exists due to a cycle in the dependency graph (i.e. the graph is not a Directed Acyclic Graph), print [].

Note: The input is given via standard input (stdin) and the output should be printed to standard output (stdout).

The problem can be solved using topological sorting. In particular, you can use Kahn's algorithm to obtain an ordering.

Mathematical Formula: A valid ordering must satisfy: For every dependency \( u \to v \), index(u) < index(v).

inputFormat

The input is given via standard input and has the following format:

The first line contains an integer ( n ) denoting the number of tasks. The second line contains ( n ) space-separated strings representing the tasks. The third line contains an integer ( m ) denoting the number of dependencies. The next ( m ) lines each contain two space-separated strings ( u ) and ( v ) representing a dependency (task ( u ) must be completed before task ( v )).

outputFormat

If a valid task ordering exists, output one line with the tasks in a valid order separated by a space. Otherwise, output a single line with [].## sample

4
a b c d
4
a b
a c
b d
c d

a b c d