TOPOSORT - Topological Sorting

no tags 

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
dev_manus: 2021-10-14 16:42:55

hint-take constraint as 10^6, or else it won't get accepted

naveen_kumar_1: 2021-07-17 03:27:57

Simple Topological sort will work !!!
First reverse sort corresponding adjacency list of vertices [ 1 to N ] to obtain lexicographically minimum sequence. Then, Do dfs in reverse order [ N to 1 ].

aggarwal1443: 2021-06-27 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: 2021-06-14 17:51:46

use min_heap not queue

abrar_al_samit: 2021-06-12 11:52:34

Huge Note : They asked for Lexicographically smallest order.

manito: 2021-06-11 12:08:33

codencode is op person

md__talha__007: 2021-05-29 17:59:45

Use kahn's algorithm using min heap(priority queue) or set.
And no need to worry about cycles as topological order doesn't exists in cyclic graph so check the size of the resulting vector after calculating topological order if it is equal to n then order exists else no

Last edit: 2021-05-29 18:00:52
sinhadipti: 2021-04-16 05:56:19

kahn's algo+set as queue

shubhi_115: 2021-04-02 15:27:57

who is send here to this question by codencode youtube channel guys

saurabh_kl: 2021-02-15 12:51:59

Java solution accepting and we have to print the solution in lexicographic smallest order if multiple solution exist
which costed me 2 times WA


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