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
da_201501181:
20170113 22:33:45
Wrong answer on test case 12 for java Anyone Please Help..where i am missing..?? 

sina_ss:
20170111 09:12:31
Nice dfs.


Roger:
20170111 03:36:56
Looks like to be too strict for JAVA. 

jason721b:
20161205 02:34:25
I am wondering whether it is possible to use Ruby to solve this. I kept getting TLE 

vengatesh15:
20161201 07:37:42
nice one :)


jatin_tayal:
20160823 20:05:45
use printf/scanf in c++


Shrish Lal Bhatnagar:
20160620 20:11:02
i felt time limit to be too strict


febrianandawp:
20160617 04:14:01
does the pair(x,y) is unique


deerishi:
20160617 01:14:49
C++14 STL <3. Priority Queue \m/


CHANDAN KUMAR:
20160615 12:18:17
In love with STL!!!!!!!!!! 
Added by:  Josef Ziegler 
Date:  20111023 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 