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
minhnguyent546: 2022-07-20 11:35:44

Don't forget the dots :)))

ryoiki_tenkai_: 2022-05-16 14:37:29

AC code: <snip>
[Simes]: No thanks, we don't want links to code.

Last edit: 2022-05-31 18:45:17
freeze0xbff: 2022-04-18 15:01:20

+1, to put full stop in Sandro fails.

afnan_d: 2021-11-29 10:09:21

anyone help me? i can not understand why my code is wrong https://ideone.com/<snip>

[Francky] => Please read the footer and use the forum.

Last edit: 2021-11-29 15:54:59
kusm_coder123: 2021-11-28 10:59:00

Don't forget to put full stop right after Sandro fails => Sandro fails.

babu_bhaiya: 2021-11-20 15:48:54

I dont' konw it is giving me WA

makhan_28: 2021-11-13 11:26:02

Dfs with sorting is wrong solution, Its giving AC because of weak test cases..
Use kahn's algo with set or priority_queue instead of queue and solve it :)

pravesh_pandey: 2021-11-10 18:26:30

use priority_queue instead of queue

yasser1110: 2021-10-22 21:15:31

Weak Test Cases
Simple DFS works but shouldn't.
People who are saying simple dfs works with sorting etc. See what
output your code gives with the following test case.
For the following test case

8 3
8 5
1 7
8 1

My code outputs
2 3 4 6 8 1 7 5

But the correct output is
2 3 4 6 8 1 5 7

For stronger test cases see https://atcoder.jp/contests/abc223/tasks/abc223_d

Last edit: 2021-10-22 21:20:26
dev_manus: 2021-10-14 16:42:55

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


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