Course Schedule II

Given n courses (0..n-1) and prerequisite pairs (a, b) meaning a requires b, return a valid order to take all courses. Print nothing (an empty line) if it's impossible (a cycle exists).

Example

Input: n = 2, prerequisite 1 requires 0 Output: 0 1

Approach

This is topological sort via Kahn's algorithm: compute each course's in-degree (number of prerequisites), start a queue with every course that has zero prerequisites, and repeatedly remove a course from the queue, append it to the order, and decrement the in-degree of everything that depended on it — adding any course whose in-degree just hit zero. If the final order doesn't include all n courses, a cycle prevented some of them from ever reaching zero in-degree.

Input format

Line 1: n Line 2: number of prerequisite pairs P Next P lines: a b meaning a requires b

Print a valid course order, space-separated — or an empty line if impossible.