TPCPPLAR - Popular

no tags 

Given a directed graph G , N vertices and M arcs. 

A node X called "acessible" to Y if there is a path from X to Y

A node X called "popular" if every node Y in V fulfill one of two conditions :

1. X is acessible to Y

2. Y is acessible to X

The Problem :  Given graph G, count the number of popular node.

 

Input

- The first line contain N and M, the number of nodes and arcs (1 <= N <= 150000; 1 <= M <= 300000)

- M next lines, each line contains x and y, there is a arcs connect from x to y.  

 

Output

- First line print number of popular nodes.

- Second line print populars node in increasing order. 

Example

Input:

5 4

1 2

3 2

2 4

4 5

Output:

3

2 4 5


hide comments
vaibhav2303: 2018-06-27 17:00:03

Test Cases are wrong / weak:-
6 8
4 1
4 3
2 4
3 5
4 6
3 2
4 5
6 2

should give answer
4
2 3 4 6
but
5
1 2 3 4 6
gets accepted

Shubham Jadhav: 2015-05-09 23:37:04

getting WA .. ;( any crucial test case?

Mew.: 2014-10-01 13:43:37

That's valid.

Jacob Plachta: 2014-10-01 13:43:37

So what if both conditions are true (X is reachable from Y and vice versa)? I assume that's valid?

Mew.: 2014-10-01 13:43:37

It can be refered that every node can go to X or X can go to

Jacob Plachta: 2014-10-01 13:43:37

I assume that at least one of the conditions for popularity needs to be satisfied, right (as opposed to exactly one)?

raj kamal: 2014-10-01 13:43:37

what does a judgement result of "0"mean? and i didn't got any points for it...weird

Mitch Schwartz: 2014-10-01 13:43:37

The way SPOJ is currently set up, problems with numeric scoring in classical section are counted as if they were challenge problems for the purposes of points/rank. So, scoring should be changed to binary, or problem should be moved to partial section.

Last edit: 2014-09-19 18:17:38
Mew.: 2014-10-01 13:43:37

MASTER JUDGE:
test 0 - WA (score=0.000000, sig=0, time=0.000000, mem=14400)
test 1 - WA (score=0.000000, sig=0, time=0.000000, mem=14400)
test 2 - AC (score=0.000000, sig=0, time=0.000000, mem=14400)
test 3 - WA (score=0.000000, sig=0, time=0.000000, mem=14400)
test 4 - AC (score=0.000000, sig=0, time=0.000000, mem=14400)
test 5 - AC (score=0.000000, sig=0, time=0.000000, mem=14400)
test 6 - WA (score=0.000000, sig=0, time=0.000000, mem=14400)
test 7 - WA (score=0.000000, sig=0, time=0.000000, mem=14400)
test 8 - WA (score=0.000000, sig=0, time=0.000000, mem=14400)
test 9 - WA (score=0.000000, sig=0, time=0.000000, mem=14400)
test 10 - WA (score=0.000000, sig=0, time=0.020000, mem=16776)
test 11 - WA (score=0.000000, sig=0, time=0.020000, mem=16776)
test 12 - WA (score=0.000000, sig=0, time=0.060000, mem=20472)
test 13 - WA (score=0.000000, sig=0, time=0.060000, mem=20472)
test 14 - WA (score=0.000000, sig=0, time=0.090000, mem=22848)
test 15 - AC (score=0.000000, sig=0, time=0.090000, mem=22848)
test 16 - WA (score=0.000000, sig=0, time=0.140000, mem=28216)
test 17 - WA (score=0.000000, sig=0, time=0.160000, mem=28792)
test 18 - AC (score=0.000000, sig=0, time=0.200000, mem=31296)
test 19 - WA (score=0.000000, sig=0, time=0.230000, mem=34304)

Jacob Plachta: 2014-10-01 13:43:37

That's weird, what does a judgment result of "25" mean?


Added by:Mew.
Date:2014-09-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64