TOPOSORT  Topological Sorting
Sandro is a well organised person. Every day he makes a list of things which need to be done and enumerates them from 1 to n. However, some things need to be done before others. In this task you have to find out whether Sandro can solve all his duties and if so, print the correct order.
Input
In the first line you are given an integer n and m (1<=n<=10000, 1<=m<=1000000). On the next m lines there are two distinct integers x and y, (1<=x,y<=10000) describing that job x needs to be done before job y.
Output
Print "Sandro fails." if Sandro cannot complete all his duties on the list. If there is a solution print the correct ordering, the jobs to be done separated by a whitespace. If there are multiple solutions print the one, whose first number is smallest, if there are still multiple solutions, print the one whose second number is smallest, and so on.
Example 1
Input: 8 9 1 4 1 2 4 2 4 3 3 2 5 2 3 5 8 2 8 6 Output: 1 4 3 5 7 8 2 6
Example 2
Input: 2 2 1 2 2 1 Output: Sandro fails.
hide comments
aman005mishra:
20200702 22:55:03
Kahn's with priority_queue...AC in one go!!!! 

hdhimanshu:
20200623 21:38:32
A good question to start with topological sorting.


tendo:
20200623 16:43:03
Even priority queue gives TLE in python. Anyone got any clue?


nandadeep_2001:
20200613 14:00:30
Good question, we need the topological sequence which is lexicographically least 

ayushpandia:
20200610 00:16:24
Python Times out??? Last edit: 20200610 00:17:03 

ayushpandia:
20200609 23:42:48
import heapq for PYTHON 

auler_:
20200519 12:21:18
You can solve it using dfs. You just need to sort each adjacency list in descending order and call the dfs function from n to 1. 

kdjonty31:
20200512 10:14:21
AC using Kahn's algorithm and priority queues. 

sudipandatta:
20200423 17:31:50
kahn's Algorithm. AC in one go!! 

dnkm:
20200416 10:34:14
c++ solution passes but when I port the same solution in Java it times out 
Added by:  Josef Ziegler 
Date:  20111023 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 