Critical Intersections

All submissions for this problem are available.
Siruseri receives a lot of rainfall during the monsoons and this used to ruin its otherwise excellent roads. A few years ago, a wise Collector converted most of the roads of Siruseri to concrete roads to avoid this nuisance. However, since there are underground cables (telephone, power, fibre optic ... ) and pipes which have to cross the roads and these cables and pipes often need fixing, the collector did not concrete any of the intersections (places where roads meet each other). The intersections were left tar covered. Cables and drains were relaid so as to cross roads only under intersections. However, during the monsoons the intersections do get ruined and this results in a lot of traffic jams on Siruseri roads. Recently, the Collector learnt of a new technology that uses small concrete blocks to pave the roads. This gives the road the strength of concrete and, further, a few of these blocks can be removed quite easily to excavate parts of the road if necessary. So he decided to use these concrete blocks to pave all the intersections in Siruseri. Paving an intersection involves stopping all the traffic through that intersection. Now, he was worried that some of these intersections could be critical. A intersection $I$ is critical if there are two other intersections $J$ and $K$ such that any route from $J$ to $K$ must necessarily pass through $I$. Notice that if $I$ is critical, then stopping all the traffic through it disconnects at least one pair of intersections from each other. You may assume that the roads of Siruseri are such that if all the intersections are usable then one can get from any intersection to any other intersection. All the roads in Siruseri permit traffic in both directions (there are no one way streets). Politicians in Siruseri love to see their names on roads and so every road segment connecting a pair of intersections has a different name. Thus a road merely connects two intersections and never pass through any other intersections. Suppose there are five intersections $I_1, I_2, I_3, I_4$ and $I_5$ and there are $6$ roads where,  Road $1$ connects $I_1$ and $I_2$  Road $2$ connects $I_2$ and $I_3$  Road $3$ connects $I_1$ and $I_3$  Road $4$ connects $I_2$ and $I_4$  Road $5$ connects $I_2$ and $I_5$  Road $6$ connects $I_5$ and $I_4$ Then, $I_2$ is a critical intersection because if all traffic through $I_2$ is blocked then there is no route from $I_4$ to $I_1$ (or $I_3$). Similarly $I_5$ is also cut off from $I_1$ and $I_3$. You can check that no other intersections is critical. Given the description of the intersections and roads in Siruseri, your task is to determine the number of critical intersections in Siruseri and list them out. ###Input: The first line of the input contains two integers $N$ and $M$. $N$ is the number of intersections in Siruseri and $M$ is the number of roads. You may assume that the intersections are numbered $1,2,...,N$. The next $M$ lines (lines $2,..., M+1$) describe the roads in Siruseri. Line $i+1$ contains two integers in the range $1,...,N$ indicating the pair of intersections connected by road $i$. ###Output: The first line of the output must contain a single integer $C$ indicating the number of critical intersections. The next $C$ lines must list out the $C$ critical intersections in increasing order, one per line. ###Constraints:  $1 \leq N \leq 300$.  $1 \leq M \leq 50000$. ###Sample Input 5 6 1 2 2 3 1 3 2 4 2 5 5 4 ###Sample Output 1 2Author:  admin2 
Date Added:  17092018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions