eolymp
bolt
Try our new interface for solving problems
Problems

The smallest Topological Sort

The smallest Topological Sort

Time limit 1 second
Memory limit 128 MiB

The directed unweighted graph is given. Find the lexicographically smallest topological ordering of 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. Each of the next m lines describes the edge of the graph — two numbers, the initial and final vertex.

Output data

Print the lexicographically smallest topological ordering of graph's vertices. If its impossible to sort graph topologically, print -1.

Examples

Input example #1
6 6
1 2
3 2
4 2
2 5
6 5
4 6
Output example #1
1 3 4 2 6 5
Author Michael Medvediev