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
garendaxe:
20210103 23:51:05
Why do we need to dfs from n to 1? 

yzs:
20201012 15:43:56
u can use dfs with set. AC in one go!!! 

kadian_:
20200924 16:19:07
If you are getting TLE (using either Kahns algo with priority queue OR by using version of dfs) make sure your cycle detection part is optimal. Cycle detection should happen in O(V+E) 

adityarakshit7:
20200819 16:03:59
kahn's algo in Python giving TLE


tridib_2003:
20200817 08:28:46
Solved using Kahn's Algo. Used set instead of queue. AC. 

dardev:
20200815 21:45:43
If there is a solution print the correct ordering, the jobs to be done separated by a whitespace.


darksun:
20200805 21:04:48
Ultimate test case if you are getting WA >


coolboy7:
20200802 08:16:09
if you want to solve it using dfs, then check out auler comment


abhinav2302:
20200723 03:51:26
Don't forget the full stop. Costed me so much time for no reason. ;_; Last edit: 20200723 05:07:15 

shukla_nk:
20200718 11:27:27
I have tried Kahn's with Priority Queue but getting TimeLimit. Could anyone please help me out with some suggestions?

Added by:  Josef Ziegler 
Date:  20111023 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 