Problem 2: Critical Intersections, (K Narayan Kumar, CMI)
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 I1, I2, I3, I4 and I5 and there are 6 roads where,
- Road 1 connects I1 and I2
- Road 2 connects I2 and I3
- Road 3 connects I1 and I3
- Road 4 connects I2 and I4
- Road 5 connects I2 and I5
- Road 6 connects I5 and I4
Then, I2 is a critical intersection because if all traffic through I2 is blocked then there is no route from I4 to I1 (or I3). Similarly I5 is also cut off from I1 and I3. 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.
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.
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, one per line.
You may assume that N ≤ 300 and M ≤ 50000.
Here is the input and output corresponding to the example discussed above.
5 6 1 2 2 3 1 3 2 4 2 5 5 4
|CPU Timelimit:||3 seconds|