P6379 [PA 2010] Planning the Roadworks

Given a directed graph with $n$ vertices and $m$ edges, find a set of edges such that after deleting this set, the reachability of the original graph remains unchanged (if a vertex was reachable before, it is still reachable), and furthermore, deleting any additional single edge will change the reachability of the original graph. Please provide one feasible solution.

The first line contains two integers $n$, $m$. The next $m$ lines each contain two numbers $x, y$, indicating that there is a directed edge from $x$ to $y$.

**This problem uses Special Judge**. In the first line, output an integer $k$, the size of the edge set. In the next $k$ lines, output one integer $e_i$ per line, meaning you delete the $e_i$-th edge in the input. The input edges are numbered starting from $1$.

#### Sample 1 Explanation One feasible solution is to delete the 2nd input edge $(1, 3)$ and the 6th input edge $(3, 4)$. --- #### Constraints For all testdata, it is guaranteed that $1 \le n \le 5000$, $1 \le m \le 100000$, and the given graph has no multiple edges or self-loops. Translated by ChatGPT 5