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
akashbhalotia:
20190523 14:26:18
How to do this using DFS method?


hellojarvis:
20190326 22:58:18
c++ WA? remove cout.tie(0) from your code. 

hellojarvis:
20190326 21:33:11
dfs version doesn't work because solution requires lexically least answer. 

Bác Ba Phì:
20190326 02:40:47
Some AC solution fail on this testcase:


manas_uniyal:
20190123 15:44:16
Don't forget the full stop. 

masterchef2209:
20190118 16:55:53
use Kahn's algo with priority_queue. good beginner question for topo sort 

masterchef2209:
20190118 16:55:52
also don't forget '.' in cycle case output :P Last edit: 20190118 16:57:20 

suyashky:
20181227 11:20:42
learned two different methods for topological sort...good question :) 

aayush_man3:
20181219 15:15:57
Make sure you have put '.' in "Sandro fails." 

behrads_1382:
20181120 12:30:43
first number have to be smallest or second number !!!??? 
Added by:  Josef Ziegler 
Date:  20111023 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 