SPOJ.com - Problem GHOSTS

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

Submit solution!

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

2013-09-23 09:39:06 Pranjali Pratik
I have 2 questions.
1. Do we allow duplicate teleports (when they do not cause 'infinite ride')..i.e. 1->5 1->5 can be built twice?
2. If we have edges 1->2, 2->3, does 1->3 need to be built? It does not cause a loop, but its 'not needed'. Any help would be appreciated. Thanks!

@Mitch: Thanks for the help! I'll work with it. :)

Last edit: 2013-09-24 19:18:43

2012-02-14 06:15:46 Priyank
Can the answer to the test case be
4 3
3 1
0 0

It is not clear which teleport should not be built.

2012-02-09 04:06:14 fitcat
@Krzysztof Lewko
Why the answer is not
6 1
1 5
6 1
0 0
The second 1 5 is duplicated and should not be built.

2012-01-30 00:44:32 Krzysztof Lewko
@bashrc the answer should be
6 1
6 1
0 0

2012-01-26 04:42:14 bashrc is back
any tricky test case plz.....

What should be the answer for this case

6
7
1 4
1 5
5 3
3 6
6 1
1 5
6 1

Last edit: 2012-01-26 07:57:23

2011-09-13 14:52:40 Problem Solver
Yes, you are right, but this is meant by default. If there's not specified if it's a->b or b->a we should assume it's a->b.
But it's not big effort to change one line of code :)

2011-09-13 14:52:40 biQar
@Problem Solver - your comment is also confusing !! u say, "They are undirected edges and it's a->b" ... i think if the edges are really undirected, then they also should be b->a. What u think ?

2011-09-13 14:52:40 Problem Solver
Come on guys, please, it's like in other graph problems. They are undirected edges and it's a->b. If it's written "it can work only in one way" it's like in life, only in one way :)

2011-09-13 14:52:40 Shiplu
@Kryzysztof Lewko: you read it carefully, where you have told these things :P, before set a problem, please make the problem statement clear to other, it is not important that is clear to you, it is important that it should be clear to us :P

Are the edges directed or undirected, if directed is it a->b or b->a,

I think, problem should be like that one would not use his/her common sense to understand the problem description.

Last edit: 2011-08-30 11:36:38

2011-09-13 14:52:40 biQar
"Every teleport can work only in one way ( to prevent collision )." -> what is the meaning of this line ? The graph is single-directional or bi-directional ? can anyone please give some more i/o ?