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
2016-01-24 17:35:33
how can it be possible !? my code print 8 6 1 4 3 5 2 (for the first sample ) and this test was passed ! and i got WA on some other test cases ! : (

Last edit: 2016-01-24 17:36:18
2015-12-06 11:29:33
Get AC from TLE after using fast input! C++14

Last edit: 2015-12-06 11:33:25
2015-10-15 08:02:29 dev
if using c++ 4.3.2 then fast io is required !!
2015-10-05 00:33:19
woooohhh...awssmmm...learnt topo without dfs... tutorial prblm bt njoyed.. ;-)
2015-09-05 20:16:56 gowtham
careful about the ordering...
2015-08-27 13:54:45 Garima
cannot understand why my program gives WA.
Tested for multiple good test cases like
#Example 1
5 3
5 1
1 2
3 4
Output - 3 4 5 1 2

#Example 2
7 4
5 1
1 2
2 3
4 6
Output - 4 5 1 2 3 6 7

Are there any other glitches like edges being < or > M or vertices outside range 1-n. In these cases should we directly output Sandro fails.

Someone with AC please help.
2015-04-22 07:10:03 Akash Goel
Thanks @Jannatul Ferdows Jenny. Got AC with 4.9.2 :D
2015-01-25 18:24:08 Jannatul Ferdows Jenny
Selected C++ 4.9 instead of C++ 4.3.2 and got AC after getting 10 TLEs. I'm speechless.
2015-01-13 12:50:38 mayank
Yes, it does requrie fast I/O!
2014-11-06 16:54:44 vishal
something wrong with 12th test case..!!
i'm getting wa. :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.