GHOSTS - Ghosts having fun

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, number of rooms in castle.

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

In next T lines a, b <= K

Rooms are numbered 1 to 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

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

hide comments
2015-07-07 20:36:27 Kushagra Juneja
What happens if we print all the edges ? Still there would be no infinite loops in the graph .....
2015-03-10 19:11:15 jkelava6
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
2015-02-07 00:11:00 AlphaDecay
Loved It!
2014-07-01 13:35:32 jkelava6
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
2014-03-02 11:19:30 ksquare
Getting WA from a very long time. Can you please check my solution id 11167565 or provide me a testcase.
2014-02-14 18:09:31 aristofanis
A small but yet important observation can help you solve the problem...
2014-02-14 07:12:13 Mitch Schwartz
@Rishav: Print the edges in the same order as they appear in the input.
2014-02-14 06:39:14 Rishav Goyal
problem statement is indeed not clear!! alot of ambiguities. Also its not clear the order of printing edges matters or not i.e. instead of

3 2
3 1

could it be
3 1
3 2

Last edit: 2014-02-14 06:39:44
2013-12-28 22:15:10 Ravi Kiran
Nice observation needed! :-)
Good problem.
2013-09-23 13:20:50 Mitch Schwartz
@#include, for the input

3
5
1 2
1 2
2 3
1 3
3 1

my AC code outputs

3 1
0 0

I don't know if duplicate teleports occur in the input though.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.