A degree has n courses numbered 1 to n and m rules. A rule a b means course a needs course b first.
Print an order in which all courses can be taken. When several courses are available at the same time, always take the smallest-numbered one first, so the answer is unique. If the rules contain a cycle, print IMPOSSIBLE.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ m ≤ 200000
- a ≠ b; no rule repeats
Input and output
- Input
- Line 1: n and m. Next m lines: a b.
- Output
- n course numbers on one line, or `IMPOSSIBLE`.
Examples
Input 1
4 3
2 1
3 1
4 3Output
1 2 3 4Course 1 comes first; then 2 and 3 are free and 2 is smaller; 4 needs 3.
Input 2
2 2
1 2
2 1Output
IMPOSSIBLEEach course needs the other, so no order exists.
Show hints
- Count, for each course, how many prerequisites it still waits on.
- Kahn's algorithm with a min-heap instead of a plain queue gives the smallest order.
Show the explanation
This is topological sorting. Draw an edge b → a for each rule and count each course's in-degree. Put every course with in-degree 0 into a min-heap. Repeatedly take the smallest, append it to the answer and decrease the in-degree of the courses that depend on it, adding any that reach 0. If fewer than n courses come out, some courses wait on each other in a cycle. A plain queue would also find a valid order; the heap makes it the smallest one, at O((n + m) log n).
Original UniCircle question. Last reviewed 22 Oct 2026.