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
ammgh:
20160124 17:35:33
how can it be possible !? my code print 8 6 1 4 3 5 2 (for the first sample ) and this test was passed ! and i got WA on some other test cases ! : ( Last edit: 20160124 17:36:18 

ducalpha:
20151206 11:29:33
Get AC from TLE after using fast input! C++14 Last edit: 20151206 11:33:25 

dev:
20151015 08:02:29
if using c++ 4.3.2 then fast io is required !! 

gullu_mishra:
20151005 00:33:19
woooohhh...awssmmm...learnt topo without dfs... tutorial prblm bt njoyed.. ;)


gowtham:
20150905 20:16:56
careful about the ordering... 

Garima:
20150827 13:54:45
cannot understand why my program gives WA.


Akash Goel:
20150422 07:10:03
Thanks @Jannatul Ferdows Jenny. Got AC with 4.9.2 :D 

Jannatul Ferdows Jenny:
20150125 18:24:08
Selected C++ 4.9 instead of C++ 4.3.2 and got AC after getting 10 TLEs. I'm speechless. 

mayank:
20150113 12:50:38
Yes, it does requrie fast I/O! 

vishal:
20141106 16:54:44
something wrong with 12th test case..!!

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