1041. Course Schedule II — Return Order

There are n courses labeled 0..n-1. Each edge [a, b] means course b must be taken before course a. Return a valid order in which to take all courses; if several exist, return the lexicographically smallest. Return an empty array if it is impossible (a cycle exists). The input is JSON {n, edges}.

Input: JSON {n, edges}.

Output: Array — a valid course order, or empty.

Examples

Input: {"n":4,"edges":[[1,0],[2,0],[3,1],[3,2]]}
Output: [0,1,2,3]
Explanation: Lexicographically smallest valid order.

Input: {"n":2,"edges":[[1,0],[0,1]]}
Output: []
Explanation: Cyclic prerequisites.

Input: {"n":1,"edges":[]}
Output: [0]
Explanation: Single course.

Constraints

• 1<=n<=10^5
• directed prerequisites

Asked by