Problem E
Edge Removal

Today Harry is studying minimum spanning trees of graphs.

A minimum spanning tree of a connected, edge-weighted undirected graph is a subset of its edges that connects all its vertices together, without any cycles and with the minimum possible total edge weight.

For example, consider the following graph:

\includegraphics[width=0.4\textwidth ]{img/original.png}

It has two minimum spanning trees, presented in two figures below, whose edges are in bold:

\includegraphics[width=0.9\textwidth ]{img/mst12.png}

Harry drew a graph on paper. However, he noticed that his graph has more than one minimum spanning trees. Harry wants to remove a minimum number of edges from the graph, such that the resulting graph has exactly one minimum spanning tree. Note that he does not need to minimize the total weight of removed edges.

Let’s reconsider the above example. If we remove the edge connecting vertices $2$ and $3$, the graph looks as below with only one minimum spanning tree (whose edges are in bold); which means that the minimum number of edges which need removing is $1$. However, this is not the only optimal solution. By removing any edges with weight at most $4$ (any of the edges $(7, 2)$, $(2, 3)$, $(4, 5)$ and $(5, 6)$), the minimum spanning tree also becomes unique. Just a reminder, the total weight of removed edges does not need minimizing.

\includegraphics[width=0.4\textwidth ]{img/delete23.png}

Please help Harry find the minimum number of edges he must remove to make the minimum spanning tree unique, and show him one way to achieve this!


The first line of the input contains a single integer $t$ — the number of test cases. Each test case is described as below:

  • The first line contains two integers $n$ and $m$ $(1 \le n \le 2 \cdot 10^5, 0 \le m \le 3 \cdot 10^5)$ — the number of vertices and edges of the graph, respectively.

  • In the next $m$ lines, the $i$-th line contains three integers: $u_ i$, $v_ i$, and $w_ i$ $(1 \le u_ i, v_ i \le n; 0 \le w_ i \le 10^9; u_ i \neq v_ i)$, indicating that there is an undirected edge connecting $u_ i$ and $v_ i$ with weight $w_ i$. It is guaranteed that no pair of vertices is connected by more than one edge.

The sum of $n$ in all test cases does not exceed $2 \cdot 10^5$. The sum of $m$ in all test cases does not exceed $3 \cdot 10^5$.


The output for each test case is presented in one line as below:

  • If the graph is not connected, print $-1$.

  • Otherwise, print $k$ — the minimum number of edges Harry needs to remove, followed by $k$ integers — the indices of the removed edges. The edges are indexed from $1$ to $m$, in the order that they appear in the input. If there are multiple solutions, you can print any of them.

Explanation of the sample input

The sample input is exactly the graph mentioned in this statement!

Sample Input 1 Sample Output 1
7 12
2 7 1
2 3 2
5 6 3
4 5 4
6 7 5
3 4 5
1 7 6
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 2

Please log in to submit a solution to this problem

Log in