GHOSTS - Ghosts having fun

no tags 

Ghost are living in big castle with K rooms.

As they have around few hundred years and very tired, they decided to buy teleports. Every teleport can work only in one way ( to prevent collision ). Ghosts have decided which teleports they want to build and in which order they should be built.

King of ghosts, Bob, asked you to check list of teleports and decide which of them do not build. He don't want ghosts having fun in infinite ride with teleports.

Input

In first line - number K<=1000, amount of rooms in castle.

In next line - number T<=300000 of teleports.

In next T lines a,b<=K

Rooms are numbered 1..K

Output

Print teleports which should not be built. End test case with 0 0

Example

Input:
4
5
2 4
4 3
3 2
1 2
3 1
Output:
3 2
3 1
0 0

hide comments
shubham_001: 2017-07-05 10:22:51

@codesmiler you can't print 1 2 instead of 3 1 because you've got 1 2 earlier till then there was no 3 1 ,so after putting teleport 1 2 you got 3 1 so remove that 3 1 and answer should be in order indeed

codesmiler: 2016-10-18 16:41:41

why can't we remove 1 2,3 2

iharsh234: 2016-08-30 21:40:01

6
7
2 1
1 3
3 4
4 2
3 5
5 6
6 1
there can be 2 answers:
1 3
0 0
or
4 2
6 1
0 0
and may be ques doesn't want us to minimize number of removed edges. max removed edges == no of cycles in graph.
Dunno why its giving WA?

Last edit: 2016-08-30 23:00:09
apar03: 2016-06-17 15:18:27

O(T*K^2) giving TLE :/

Last edit: 2016-06-17 15:18:58
shikhar0037: 2016-06-02 21:30:27

Finally accepted after getting many RTE :) very silly mistake

Kushagra Juneja: 2015-07-07 20:36:27

What happens if we print all the edges ? Still there would be no infinite loops in the graph .....

jkelava6: 2015-03-10 19:11:15

OK, it seems that after ages I see a bug in my code.
And to me it looks like fixing it made my code work in T K^2, which is TLE!
No, it is ACCEPTED?

Last edit: 2015-03-10 19:11:30
AlphaDecay: 2015-02-07 00:11:00

Loved It!

jkelava6: 2014-07-01 13:35:32

Well, if I am right ( I am still coding ), there is small trick... But as I see some people are asking, you have to output teleports in the same order you input them, just with 99% you output less.
You don't have to minimize your list!

Last edit: 2014-07-01 13:41:01
Rishab Banerjee: 2014-05-09 23:00:35


Last edit: 2014-05-10 18:53:53

Added by:Krzysztof Lewko
Date:2011-08-25
Time limit:0.129s-0.728s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64