380. An Order That Respects Every Arrow
The edges are directed, and an edge u v means u must come before v.
Think of subjects with prerequisites.
Print an order of all n vertices in which every edge points forwards. Print
IMPOSSIBLE if no such order exists.
Several orders are usually valid, so a judge cannot accept any of them. Print the LEXICOGRAPHICALLY SMALLEST one: whenever more than one vertex is ready, take the smallest-numbered.
That single rule turns the queue from problem 379 into a priority queue. Both peel vertices whose in-degree has reached 0; a plain queue takes whichever became ready first, and a priority queue takes the smallest.
And IMPOSSIBLE is not a separate check. It is the exact situation problem 379
detects: if you cannot place all n vertices, a cycle is in the way.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
directed edges. Each of the next m lines contains two integers u and v,
a directed edge from u to v and NOT from v to u. Vertices are numbered
1 to n.
Output
Print the n vertex numbers on one line separated by single spaces, or the
single word IMPOSSIBLE.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.