Given a directed unweighted graph. It is necessary to sort it topologically.
Input: The first line contains two natural numbers n and m (1≤n≤10
5, 1≤m≤10< sup>5) — the number of vertices and edges in the graph, respectively. Next m lines list the edges of the graph. Each edge is given by a pair of numbers — the numbers of the start and end vertices, respectively.
Output: Print any topological sort of the graph as a sequence of vertex numbers. If the graph cannot be topologically sorted, print −1.
The first line contains the number of vertices N and edges M.
Examples
| # |
Input |
Output |
| 1 |
4 4
14
4 3
4 2
3 2 |
1 4 3 2 |