## 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 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?