Schedule the Courses

Difficulty: 1600 4000 ms 128 MB

graphs sorting

Courses have prerequisites (edge u → v means u must precede v). Print the lexicographically smallest valid ordering, or IMPOSSIBLE on a cyclic dependency.

Input: the first line has N and M; each of the next M lines has a directed edge u → v (1-based).

Output: the smallest topological order (space-separated), or IMPOSSIBLE.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴
• multiple edges and self-loops may appear

Sample Tests

4 3
1 2
3 2
3 4

1 3 2 4

2 2
1 2
2 1

IMPOSSIBLE

Read the Editorial