F. Almost Bipartite Graph
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph consisting of $$$n$$$ vertices and $$$m$$$ edges. The graph has no self-loops or multiple edges. It is not guaranteed that the given graph is connected.

Recall that a graph is called bipartite if it is possible to color all the vertices with two colors such that no edge connects two vertices of the same color.

Your task is to determine whether it is possible to remove no more than $$$k$$$ edges in such a way that the resulting graph becomes bipartite.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 10^3$$$; $$$1 \le m \le 10^3$$$; $$$1 \le k \le 10$$$) — the number of vertices and edges in the graph, and the maximum number of edges that can be removed.

The next $$$m$$$ lines follow, where the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$), representing an edge between vertices $$$x_i$$$ and $$$y_i$$$. The given graph has no self-loops or multiple edges.

Output

In the first line, print the number of edges (no more than $$$k$$$) that need to be removed for the graph to become bipartite. In the second line, output the indices of the edges.

If such a set of edges does not exist, output -1 in a single line.

If there are multiple suitable sets of edges, output any of them. The indices of the edges can be output in any order. Edges are numbered from $$$1$$$ to $$$m$$$ in order of the input.

Examples
Input
4 5 1
1 2
1 3
2 3
2 4
3 4
Output
1
3 
Input
4 6 1
1 2
2 3
4 2
3 4
3 1
1 4
Output
-1
Input
5 3 2
1 2
2 3
4 5
Output
0
Input
5 6 10
1 2
3 2
5 3
3 4
4 5
1 4
Output
6
1 2 3 4 5 6