Task Scheduling with Dependencies

You are given a set of tasks, each with a specific duration, and a list of dependencies between these tasks. A dependency (u, v) means that task u must be completed before task v can start. Your objective is to determine a valid order in which all tasks can be performed so that all dependencies are met. If such an ordering exists, print the total duration (which is simply the sum of all task durations) and one valid order of tasks. If it is not possible to complete all tasks due to cyclic dependencies, print IMPOSSIBLE.

Note: The ordering is obtained using a topological sort. If multiple valid orders exist, output the one determined by your algorithm.

Mathematically, let \(T = \{1, 2, \ldots, n\}\) be the set of tasks, and let the dependencies be represented as directed edges \(E\) where if \((u,v) \in E\) then task \(u\) must come before task \(v\). A valid scheduling exists if and only if the directed graph \(G=(T,E)\) is acyclic.

inputFormat

The input consists of several lines:

1. The first line contains a single integer \(n\) representing the number of tasks.
2. The second line contains \(n\) space-separated integers, where the \(i\)-th integer represents the duration of task \(i\).
3. The third line contains a single integer \(m\) representing the number of dependencies.
4. The next \(m\) lines each contains two space-separated integers \(u\) and \(v\), indicating that task \(u\) must be completed before task \(v\).

outputFormat

If it is possible to complete all tasks, print a single line containing the total duration followed by a valid topological order (tasks separated by a space). If it is impossible to complete all tasks due to cyclic dependencies, print IMPOSSIBLE (without quotes).

3
3 2 4
0

9 1 2 3