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 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.

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

hide comments
2020-08-05 21:04:48
Ultimate test case if you are getting WA -->
6 4
5 1
1 2
2 3
4 6
4 5 1 2 3 6 <-- and just see this way your lexicographic order is correct
2020-08-02 08:16:09
if you want to solve it using dfs, then check out auler comment
2020-07-23 03:51:26
Don't forget the full stop. Costed me so much time for no reason. ;_;

Last edit: 2020-07-23 05:07:15
2020-07-18 11:27:27
I have tried Kahn's with Priority Queue but getting TimeLimit. Could anyone please help me out with some suggestions?
2020-07-02 22:55:03
Kahn's with priority_queue...AC in one go!!!!
2020-06-23 21:38:32
A good question to start with topological sorting.
first, find a cycle in DG and then just use priority_queue with vector and apply dfs from n to 1.
u will get AC.

Last edit: 2020-06-23 21:39:35
2020-06-23 16:43:03
Even priority queue gives TLE in python. Anyone got any clue?

[NG]: The dataset is huge, ensure your I/O is up to it --> https://www.spoj.com/ranks/INTEST/lang=PYTH%203.2.3 . Submit in PyPy if still in trouble.

Last edit: 2020-06-23 16:52:29
2020-06-13 14:00:30
Good question, we need the topological sequence which is lexicographically least
2020-06-10 00:16:24
Python Times out???

Last edit: 2020-06-10 00:17:03
2020-06-09 23:42:48
import heapq for PYTHON
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.