BIA - Bytelandian Information Agency

Bytelandian Information Agency (BIA) uses a net of n computers. The computers are numbered from 1 to n, and the computer number 1 is a server. The computers are connected by one-way information channels. Every channel connects a pair of computers. The whole network is organised in such a way that one can send information from the server to any other computer either directly or indirectly.

When BIA acquires new information, the information is put on the server and propagated in the net. The chief of BIA considers what would happen if one computer stopped working (was blown away by terrorists for example). It could happen that some other computers would stop receiving information from the server, because the broken computer was a necessary transmitter. We will call such computers critical. For example in the situation in the picture below the critical computers are 1 and 2. 1 is the server and all information sent from the server to 3 has to go through 2.

BIA computer net

Task

Write a program which

  • reads a description of the net from standard input,
  • finds all critical computers.
  • writes the numbers of critical computers to standard output.

Input

Ten test cases (given one under another, you have to process all!). Each test case consists of several lines. In the first line there are numbers n and m. n denotes the number of computers in the net,(2<=n<=5000). m denotes the number of information channels, n-1<=m<=200000. The following m lines describes a single information channel and consist of two integer numbers a and b separated by a space. It means the computer a sends information to computer b by that channel. You may assume there are no two channels which start and end at the same points a, b.

Output

For every testcase your program should write two lines. In the first line k - the number of critical computers in the net. In the second line k numbers separated by single spaces - the numbers of critical computers in increasing order.

Example

Input:
4 5
1 2
1 4
2 3
3 4
4 2
[and 9 test cases more]

Output:
2
1 2
[and 9 test cases more]

Warning: large Input/Output data, be careful with certain languages

Added by:Adam Dzedzej
Date:2004-06-14
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Internet Contest Pogromcy Algorytmow (Algorithm Tamers)
Round IV, 2003

hide comments
2021-04-05 06:06:15
Use Lengauer-Tarjan algorithm
2015-01-23 19:33:26 Eric Gross
EDIT: I got my answer.

Last edit: 2015-01-26 04:39:11
2013-08-31 11:46:39 devD
any tricky testcases please !! Getting
WA
2012-05-05 15:31:12 Ashish Raj
hi..my code is in java..it is working fine in netbeans but here it is giving me NZEC error..what to do?
2010-11-28 06:45:27 cherudim
nice problem

Last edit: 2013-03-04 13:03:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.