eolymp
bolt
Try our new interface for solving problems
Problems

Topological Sort

Topological Sort

Time limit 2 seconds
Memory limit 128 MiB

Given a directed unweighted graph. Topologically sort its vertices.

Input data

The first line contains the number of vertices n~(1 \le n \le 10^5) and the number of edges m~(1 \le m \le 10^5) in a graph. In the following m lines, the edges of the graph are listed, each of which is defined by a pair of numbers — the indices of the starting and ending vertices.

Output data

Print any topological sort of the graph as a sequence of vertex numbers. If the graph cannot be topologically sorted, then print -1.

Examples

Input example #1
6 6
1 2
3 2
4 2
2 5
6 5
4 6
Output example #1
4 6 3 1 2 5
Author Vitaly Goldstein
Source Winter School, Kharkov, 2011, Day 9