eolymp
bolt
Try our new interface for solving problems
Problems

The smallest Topological Sort

The smallest Topological Sort

The directed unweighted graph is given. Find the lexicographically smallest topological ordering of its vertices. \InputFile 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. \OutputFile Print the lexicographically smallest topological ordering of graph's vertices. If its impossible to sort graph topologically, print $-1$. \includegraphics{https://static.e-olymp.com/content/c8/c892750f0f88eb3a20f84a3344f54f2268287c3f.gif}
Time limit 1 second
Memory limit 128 MiB
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