Task Scheduling with Dependencies

You are given n tasks numbered from 1 to n and m dependency relations. Each dependency is given as a pair (a, b) which means that task a depends on task b, i.e. task b must be completed before task a can start.

Your objective is to determine an order in which all tasks can be completed while respecting the dependencies. If there is more than one valid order, you may output any one of them. However, if it is impossible to complete all tasks because of a cyclic dependency, then output an empty result.

The problem is based on topological sorting. In terms of graph theory, tasks represent nodes and dependencies represent directed edges. A valid order exists if and only if the graph is a Directed Acyclic Graph (DAG).

Formally, given a graph with n nodes and m directed edges, you are to find a permutation \(P = [p_1, p_2, \dots, p_n]\) of tasks such that for every dependency \((a, b)\) (meaning an edge from \(b\) to \(a\)), the task \(b\) appears before task \(a\) in \(P\). If no such ordering exists, output an empty list.

Note: All formulas are written in LaTeX format. For example, a valid topological ordering \(P\) must satisfy \(\forall (a,b):\; \text{index}(b) < \text{index}(a)\).

inputFormat

The input is read from stdin and consists of multiple lines:

• The first line contains two integers: n (the number of tasks) and m (the number of dependencies).
• The next m lines each contain two integers a and b, indicating that task a depends on task b (i.e., task b must be completed before a).

Tasks are numbered from 1 to n.

outputFormat

Output to stdout a single line representing a valid order of tasks separated by a single space. If it is impossible to complete all tasks due to a cyclic dependency, output an empty line.

## sample

4 3
2 1
3 1
4 2

1 2 3 4

</p>