Simple Cycles Edges
Contest: Educational Codeforces Round 42 (Rated for Div. 2)
Difficulty rating: 2400
Tags: dfs and similar, graphs, trees

You are given an undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges. The graph does not necessarily connected. Guaranteed, that the graph does not contain multiple edges (more than one edges between a pair of vertices) or loops (edges from a vertex to itself).

A cycle in a graph is called a simple, if it contains each own vertex exactly once. So simple cycle doesn't allow to visit a vertex more than once in a cycle.

Determine the edges, which belong to exactly on one simple cycle.

Input format:
The first line contain two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 100\,000$$$, $$$0 \le m \le \min(n \cdot (n - 1) / 2, 100\,000))$$$ — the number of vertices and the number of edges.

Each of the following $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — the description of the edges.

Output format:
In the first line print the number of edges, which belong to exactly one simple cycle.

In the second line print the indices of edges, which belong to exactly one simple cycle, in increasing order. The edges are numbered from one in the same order as they are given in the input.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 3
1 2
2 3
3 1

Example output:
3
1 2 3

Example input:
6 7
2 3
3 4
4 2
1 2
1 5
5 6
6 1

Example output:
6
1 2 3 5 6 7

Editorial:
To solve this problem, it is good to know about fundamental set of cycles.
Briefly, in the graph it is easy to select such a minimal set of cycles $$$C$$$ that any other cycle can be obtained as XOR of some subset of cycles from $$$C$$$. This set is also called the fundamental set of cycles. To find it in a connected graph, you can find any carcass and, alternately, independently add to this carcass each of the edges that are not entered into it. When each such edge is added to the carcass, its cycle closes. The set of these cycles is a fundamental set of cycles. Thus, if the graph is connected, then the size of the fundamental set of cycles is exactly $$$m-n+1$$$.
It is easy to see that if an edge belongs to exactly one cycle from the fundamental set of cycles, then it belongs to exactly one simple cycle.
We solve the problem independently for each connected component. For a connected component, it finds its carcass by a search in depth, and each edge that does not enter the search tree into the depth will close a cycle. We only take into account those cycles that do not intersect along the edges. We should print only them in the form of a set of edges.
If the carcass was built with a search in depth, then each cycle represents a path from the vertex to the child (plus the reverse edge). Thus, the problem now is: a set of pairs of vertices (a vertex and its descendant) that specify a set of paths from top to bottom is given in the tree. It is required to select those paths that do not intersect with any other paths from this set.
To find such ways quickly it is possible with help of DSU (system of non-intersecting subsets) on paths. On the edge, you should store the -1 mark or the path number to which it belongs. When passing the edges without marking, it should be marked by this path. When passing an edge with a mark, it is necessary to merge two paths into the DSU, because they intersect. After processing the path, for all the vertices of the path, the ancestor should be reassign to the top vertex of the path. Because if we do not make this we will repeatedly go through the same path.
Using the following code, we find for each vertex its depth in the depth search tree and all the back edges (an array be):
Using the following code, we process all paths (actually cycles), merging the intersecting ones.
Let $$$pp$$$ — it is an original array of ancestors in depth search tree (because array $$$p$$$ has been changed by the code above). Now, it is sufficient to the answer to take such paths plus the corresponding reverse edge that do not intersect with others (that is, the size of the DSU component is 1):
This problem has another solution, based on the allocation of the doubly connected components with the help of the corresponding linear algorithm.