#C2502. Task Dependency Order
Task Dependency Order
Task Dependency Order
You are given n tasks labeled from 1 to n and m dependency relations between them. Each dependency is given as a pair of integers a and b, which means that task a must be completed before task b can start (i.e., $a \to b$). Your goal is to determine a valid ordering of all tasks such that all the dependencies are satisfied.
If there are multiple valid orders, any one of them is acceptable. However, if it is impossible to complete all tasks due to cyclic dependencies, output Impossible
.
Note: The input and output are handled through standard input (stdin) and standard output (stdout) respectively.
inputFormat
The first line contains two integers n and m representing the number of tasks and the number of dependencies respectively. The following m lines each contain two integers a and b, representing a dependency from task a to task b.
\(1 \leq a, b \leq n\)
outputFormat
If a valid ordering exists, output a single line containing the tasks in one valid order, separated by a space. If no such ordering exists due to a cycle, output Impossible
.
3 0
1 2 3
</p>