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
2022-07-29 15:46:30
done in 42nd go without bitset (˃̣̣̥ᴖ˂̣̣̥)
2022-06-05 09:00:46
why cant we use a DSU?
instead of union -> we make {a - > b}, a as parent of B.
when new node comes, check if a & b have same parent, if yes, print the edge
2021-01-12 12:16:37
any hint ?? how to solve problem..??
2019-08-28 15:38:06
nice concept but bad problem statement...
to make things clear, all edges are directed from a to b, and we have to build edges according to the order they appear in input. If the current edge does not form a cycle with edges already built, we build this edge; otherwise, we report the current edge and ignore it.
2018-08-28 02:39:37 narek
Hint: bitset :)
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
2016-10-18 16:41:41
why can't we remove 1 2,3 2
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
2016-06-17 15:18:27
O(T*K^2) giving TLE :/

Last edit: 2016-06-17 15:18:58
2016-06-02 21:30:27 shikhar0037
Finally accepted after getting many RTE :) very silly mistake
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.