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

hide comments
Krzysztof Lewko: 2011-09-13 14:52:40

Everything's clear, just read it carefully.
Ghosts want to build each teleport in exact order, so 1st teleport can be build 1st. If there is no possibility to build it, just ignore it and go to next teleport on the list. Again - no possibility ? Ignore. Otherwise, build it.

biQar: 2011-09-13 14:52:40

description not clear !! @Krzysztof Lewko

Krzysztof Lewko: 2011-09-13 14:52:40

For example when we have 3 rooms. And built teleports : 1->2, 2->3 then when next teleport is 3->1 then we can't build it, because of "infinite ride".

Siarhei Kulik: 2011-09-13 14:52:40

What does "should not be built" mean? Are we have to build maximal number of teleports? If not, can we simply remove all of them (then there will be no infinite ride at all) ? This things are more important that King's of ghosts name but described in statement a bit unclear :)

Last edit: 2011-08-25 18:29:56

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