#C4925. Module Completion Order
Module Completion Order
Module Completion Order
You are given \(n\) modules numbered from 1 to \(n\) and \(m\) dependency relations. Each relation \((a, b)\) indicates that module \(a\) must be completed before module \(b\). Your task is to determine a valid order in which all modules can be completed.
If there exists more than one valid ordering, output the lexicographically smallest one (i.e. the one that comes first when compared element by element). If no valid ordering exists, output IMPOSSIBLE
.
This problem can be solved using topological sorting. One common approach is Kahn's algorithm using a priority queue to always pick the smallest available module.
inputFormat
The input is read from standard input.
The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of modules and \(m\) is the number of dependencies.
The next \(m\) lines each contain two integers \(a\) and \(b\), meaning that module \(a\) must be completed before module \(b\).
outputFormat
If a valid ordering exists, print the lexicographically smallest valid ordering of the modules as space-separated integers on one line.
If no such ordering exists because of a cycle, print IMPOSSIBLE
.
4 4
1 2
1 3
3 4
2 4
1 2 3 4
</p>