eolymp
bolt
Try our new interface for solving problems
Problems

Magnetic Cushions

Magnetic Cushions

The City of the Future is built up with skyscrapers. To move between them and transport parking some of skyscrapers triples are connected with triangular cushions made from unipolar magnets. Each cushion connects exactly $3$ skyscrapers and a top view on it is a triangle with vertices in skyscrapers. This allows moving freely between the skyscrapers. The pillows can be constructed at different levels, so one skyscraper can be connected with different couples using different pillows, so two skyscrapers can be connected with multiple pillows (either with different third skyscrapers or with the same). For example, there may be two cushions at different levels between skyscrapers $1, 2$ and $3$ and moreover, a magnetic cushion between $1, 2$ and $5$. The system of magnetic pillows is organized so that you can use them to get from one skyscraper to any other in this city (from one pillow to another you can move inside a skyscraper), but maintaining each of them requires a lot of energy. Write a program that finds which magnetic pillows can not be removed from the city structure, because removal of even just one of them leads to the fact that there exist skyscrapers from which now you can not get to some other skyscrapers, and people will become very sad. \InputFile The first line contains two integers $n$ and $m~(3 \le n \le 10^5, 1 \le m \le 10^5)$ --- the number of skyscrapers in the city and the number of magnetic pillows correspondingly. In each of the next $m$ lines three integers are given --- the numbers of skyscrapers, connected with a cushion. The skyscrapers are numbered with integers from $1$ to $n$. It is guaranteed that the given magnetic cushions allow you to move from any skyscraper to any other. \OutputFile Print the number of magnetic pillows, which to turn off is impossible without breaking the connectivity in the city. If this number is non-zero, print in the next line their numbers. The numbers should correspond to the order in which the cushions are listed in the input. The numbering starts from one. \includegraphics{https://static.e-olymp.com/content/19/19572f221bf485864bf0a882a3a8a83158a75528.gif}
Time limit 2 seconds
Memory limit 128 MiB
Input example #1
5 4
1 2 3
2 4 3
1 2 4
3 5 1
Output example #1
1
4
Input example #2
3 2
1 2 3
3 2 1
Output example #2
0
Input example #3
3 1
1 2 3
Output example #3
1
1