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
mt6170078: 2019-10-17 21:42:03

java is giving TLE even after using priority queue... :'(

Last edit: 2019-10-17 21:42:25
daasdaham80: 2019-06-28 09:08:31

Cool problem, i learned kahns algo and priority queue in one go

harshraj22aug: 2019-06-25 21:25:04

Learnt Kahn's algorithm. Great question to try after learning it .

akashbhalotia: 2019-05-23 14:26:18

How to do this using DFS method?

hellojarvis: 2019-03-26 22:58:18

c++ WA? remove cout.tie(0) from your code.

hellojarvis: 2019-03-26 21:33:11

dfs version doesn't work because solution requires lexically least answer.

Bác Ba Phì: 2019-03-26 02:40:47

Some AC solution fail on this testcase:
6 5
1 5
5 3
5 2
2 4
2 6
The correct output is: 1 5 2 3 4 6

manas_uniyal: 2019-01-23 15:44:16

Don't forget the full stop.

masterchef2209: 2019-01-18 16:55:53

use Kahn's algo with priority_queue. good beginner question for topo sort

masterchef2209: 2019-01-18 16:55:52

also don't forget '.' in cycle case output :P

Last edit: 2019-01-18 16:57:20

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