E. Maximizing SCCs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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.

Examples
Input
4 5 1
1 2
2 3
1 4
4 3
3 1
Output
4
1
Input
7 7 0
1 2
2 3
3 4
4 5
5 6
6 7
7 1
Output
7
Note

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 :)