Challenge: Course Order

Lab Python Intermediate 20 points

There are n courses numbered 0 … n − 1 and some rules a b meaning “course a must be taken before course b”. Print an order to take all courses using Kahn's algorithm. When several courses are ready, always take the smallest number first (use a heap). If it's impossible, print impossible.

Input

Line 1: n m. Then m lines a b.

Output

The order, or impossible.

Example

Input

Output

2 3 1 0

Sample input available Sample output available

Editor

Python

Hints

indeg[b] counts how many courses must come before b.

Start with every course whose indeg is 0.

If you finish with fewer than n courses, there's a cycle.

Solution explanation

A heap instead of a plain queue makes the order unique: the smallest ready course always goes next.

Show solution

import heapq
n, m = map(int, input().split())
after = [[] for _ in range(n)]
indeg = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    after[a].append(b)
    indeg[b] += 1
ready = [v for v in range(n) if indeg[v] == 0]
heapq.heapify(ready)
order = []
while ready:
    v = heapq.heappop(ready)
    order.append(v)
    for w in after[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            heapq.heappush(ready, w)
print(" ".join(map(str, order)) if len(order) == n else "impossible")

Output

Answer