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
naveen_kumar_1:
20210717 03:27:57
Simple Topological sort will work !!!


aggarwal1443:
20210627 17:25:31
If getting wrong answer with simple topological sort then just sort values at corresponding vertex and do topological sort from N till 1 :) 

rituranjan:
20210614 17:51:46
use min_heap not queue


abrar_al_samit:
20210612 11:52:34
Huge Note : They asked for Lexicographically smallest order. 

manito:
20210611 12:08:33
codencode is op person


md__talha__007:
20210529 17:59:45
Use kahn's algorithm using min heap(priority queue) or set.


sinhadipti:
20210416 05:56:19
kahn's algo+set as queue 

shubhi_115:
20210402 15:27:57
who is send here to this question by codencode youtube channel guys 

saurabh_kl:
20210215 12:51:59
Java solution accepting and we have to print the solution in lexicographic smallest order if multiple solution exist


garendaxe:
20210103 23:51:05
Why do we need to dfs from n to 1? 
Added by:  Josef Ziegler 
Date:  20111023 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 