406987: GYM102646 E Maximizing SCCs

In a directed graph, two vertices $$$A$$$ and $$$B$$$ are called strongly connected if there exists a path from $$$A$$$ to $$$B$$$ and a path from $$$B$$$ to $$$A$$$.

A strongly connected component is a subset of vertices where all pairs of vertices in the component are strongly connected, and the subset is of maximal size - there does not exist another vertex that can be added to the subset satisfying the first condition.

Timmy has a directed graph with $$$n$$$ vertices and $$$m$$$ edges, where all pairs of vertices are strongly connected. He has to select a subset of exactly $$$k$$$ edges in this graph, then remove all others. Of all subsets of $$$k$$$ edges, he wants to find a subset that creates a graph with the maximum possible number of strongly connected components. Nobody really knows why he wants this, not even Timmy himself, but that's your task for this problem.

The first line contains three space-separated integers: $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, $$$m$$$ $$$(n \leq m \leq 2 \cdot 10^5)$$$, and $$$k$$$ $$$(0 \leq k < n)$$$. The next $$$m$$$ lines contain two space-separated integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v \leq n)$$$, denoting a directed edge between $$$u$$$ and $$$v$$$. No edge is repeated, and there are no self-loops.

On the first line, print the maximum possible number of strongly connected components. On the next line, print the indices of edges in any subset of size $$$k$$$ that achieves this maximum. You can print any valid subset.

4 5 1
1 2
2 3
1 4
4 3
3 1

4
1 

7 7 0
1 2
2 3
3 4
4 5
5 6
6 7
7 1

7

In the first example, taking any edge will give you $$$n$$$ components, because it requires at least two edges for there to be a path from $$$u$$$ to $$$v$$$ and $$$v$$$ to $$$u$$$ for any $$$u, v$$$.

In the second example, no edges are taken, so there are always $$$n$$$ components.

Create your own, stronger samples :)