Task Scheduling with Dependencies

You are given a set of tasks and a list of dependency pairs. Each dependency pair \((x, y)\) indicates that task y must be completed before task x (i.e., \(y \rightarrow x\)). Your goal is to determine an order in which all tasks can be completed such that all dependency constraints are satisfied. In other words, for every dependency \((x, y)\), task \(y\) should appear before task \(x\) in the ordering.

If a valid ordering exists, print the tasks in that order, separated by spaces. If there exists a cycle that prevents completing all tasks, output an empty line.

inputFormat

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

• The first line contains an integer \(n\), the number of tasks.
• The second line contains \(n\) space-separated strings representing the task names.
• The third line contains an integer \(m\), the number of dependency pairs.
• Each of the next \(m\) lines contains two space-separated strings \(x\) and \(y\), indicating that task \(x\) depends on task \(y\) (i.e., \(y\) must come before \(x\)).

outputFormat

If a valid ordering exists, output a single line with the tasks in a valid order, separated by spaces. If no valid ordering exists because of a cyclic dependency, output an empty line.

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

d b a c