AT_arc225_c [ARC225C] K Spanning Tree

You are given a simple connected undirected graph $ G $ with $ N $ vertices and $ M $ edges. Edge $ i $ connects vertices $ a_i $ and $ b_i $ , and has weight $ c_i $ . Here, each edge's weight is $ 0 $ or $ 1 $ . You are given a non-negative integer $ K $ . Determine whether there exists a spanning tree of $ G $ such that the sum of the weights of the edges composing the spanning tree is exactly $ K $ , and if one exists, find one. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each case is given in the following format: > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ \vdots $ $ a_M $ $ b_M $ $ c_M $

Output $ T $ lines. The $ i $ -th line should contain the answer for $ \text{case}_i $ . If there is no spanning tree satisfying the condition, output `-1`. Otherwise, let $ x_1,x_2,\cdots,x_{N-1} $ be the numbers of the edges composing a spanning tree for that case, and output them in the following format: > $ x_1 $ $ x_2 $ $ \cdots $ $ x_{N-1} $ $ x_1,x_2,\cdots,x_{N-1} $ can be in any order. The edge numbers correspond to the input order within each case. If multiple solutions exist, any of them is accepted.

### Sample Explanation 1 For the first case, the graph composed of edges $ 1,4,5 $ is a spanning tree of $ G $ , and the sum of its edge weights is $ 2 $ , so it satisfies the condition. Outputs such as `2 4 5` and `4 1 5` are also accepted. For the second case, the sum of the edge weights of a spanning tree of graph $ G $ cannot be $ 1 $ . ### Constraints - $ 1 \le T \le 10^5 $ - $ 2 \le N \le 2\times 10^5 $ - $ N-1 \le M \le \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right) $ - $ 0 \le K \le N-1 $ - $ 1 \le a_i,b_i \le N $ - $ c_i=0 $ or $ c_i=1 $ . - The graph $ G $ is simple and connected. - The sum of $ N $ over all test cases is at most $ 2\times 10^5 $ . - The sum of $ M $ over all test cases is at most $ 2\times 10^5 $ . - All input values are integers.