There are n courses, numbered 0 to n − 1. A pair a b means course b must be taken before course a. Find an order to take every course, taking at each moment the smallest-numbered course whose prerequisites are all done. If no order exists, say so.
Input
The first line has n and m (1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5 × 10⁴). Each of the next m lines has a pair a b (a ≠ b).
Output
The courses in order, separated by spaces, or impossible.
Examples
Example 1 · Input
4 4 1 0 2 0 3 1 3 2
Expected output
0 1 2 3
Example 2 · Input
2 2 0 1 1 0
Expected output
impossible
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Count each course's prerequisites (its in-degree), and list which courses each one unlocks.
Hint 2
Keep the ready courses in a heap (heapq), so the smallest number is always taken first.
Hint 3
If fewer than n courses come out, there is a cycle: print impossible.
Solution
Show one correct solution (try it yourself first)
import heapq
n, m = map(int, input().split())
needs = [0] * n
unlocks = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, input().split())
needs[a] += 1
unlocks[b].append(a)
ready = [c for c in range(n) if needs[c] == 0]
heapq.heapify(ready)
order = []
while ready:
c = heapq.heappop(ready)
order.append(c)
for nxt in unlocks[c]:
needs[nxt] -= 1
if needs[nxt] == 0:
heapq.heappush(ready, nxt)
print(*order) if len(order) == n else print("impossible")