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 space. 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
auler_: 2020-05-19 12:21:18

You can solve it using dfs. You just need to sort each adjacency list in descending order and call the dfs function from n to 1.

kdjonty31: 2020-05-12 10:14:21

AC using Kahn's algorithm and priority queues.

sudipandatta: 2020-04-23 17:31:50

kahn's Algorithm. AC in one go!!

dnkm: 2020-04-16 10:34:14

c++ solution passes but when I port the same solution in Java it times out

varuntumbe: 2020-03-31 19:21:48

WATCH OUT FOR '.' in Sandro fails. and S is capital

dchowdhary: 2020-03-08 18:50:45

I am getting TLE in java even after using priority queue. Any help?

amantu_amir: 2020-02-26 17:14:18

AC using Binary Search and Topological sort.

md_meraj1319: 2020-02-10 20:59:57

AC in 1 go. just use topological sort with Set in place of Queue.

thakkar2804: 2020-02-01 13:09:29

sort the adjacency list in descending order and then apply dfs for n to 1.

nadstratosfer: 2020-01-28 00:24:38

It's possible with Python:
https://www.spoj.com/ranks/TOPOSORT/lang=PYTH%202.7
https://www.spoj.com/ranks/TOPOSORT/lang=PYTH%203.2.3

The idea is to ensure your code is efficient, which is best practiced with problems where TL is more lenient so you get to see what kind of changes can affect the runtime. Also check the constraints here, is your I/O up to the task? Try INTEST.


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