Course Completion Order

You are given \(N\) courses numbered from 1 to N and \(M\) prerequisite relationships. Each prerequisite is represented as a pair \((a, b)\) indicating that course \(b\) must be taken before course \(a\). Your task is to determine any valid order for completing all courses. If there is a cycle among the courses (i.e. no valid order exists), output an empty list [].

Formally, given integers \(N\) and \(M\) and a list of pairs \((a, b)\), find a sequence \(S = [s_1, s_2, \dots, s_N]\) such that for every prerequisite pair \((a, b)\), course \(b\) appears before course \(a\) in \(S\). If no such ordering exists, output [].

You can use topological sorting (for example, Kahn's algorithm) to solve this problem.

inputFormat

The input is read from standard input (stdin) and has the following format:

N M
a1 b1
a2 b2
... 
aM bM

Here, the first line contains two integers \(N\) and \(M\) representing the number of courses and the number of prerequisite pairs respectively. Each of the next \(M\) lines contains two integers \(a\) and \(b\) which means that to take course \(a\) you must first complete course \(b\).

outputFormat

Output to standard output (stdout) a single line. If a valid course ordering exists, print the ordered course numbers separated by a space. Otherwise, print an empty list: [].

4 3
2 1
3 2
4 3

1 2 3 4