AT_arc225_c.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.

给你一个包含 $N$ 个顶点和 $M$ 条边的简单连通无向图 $G$。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，其权重为 $c_i$。其中，每条边的权重为 $0$ 或 $1$。

再给你一个非负整数 $K$。请判断图 $G$ 是否存在一棵生成树，使得该生成树中所有边的权重之和恰好等于 $K$；若存在，请找出这样的一棵生成树。

你将收到 $T$ 组测试数据，请对每组数据分别求解。

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$

输入从标准输入中以如下格式给出：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每个测试用例以如下格式给出：

$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.

输出 $T$ 行。第 $i$ 行应为第 $i$ 个测试用例的答案。

若不存在满足条件的生成树，则输出 -1。

否则，设 $x_1,x_2,\cdots,x_{N-1}$ 为构成该测试用例中某棵生成树的各条边的编号，并按如下格式输出：

$x_1$ $x_2$ $\cdots$ $x_{N-1}$

$x_1,x_2,\cdots,x_{N-1}$ 的顺序可任意。边的编号对应于每个测试用例中输入的边的顺序。若存在多个可行解，输出其中任意一个即可。

Sample 1 Explanation:
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.

样例 1 解释：
对于第一组测试数据，由边 $1,4,5$ 构成的图是图 $G$ 的一棵生成树，其边权之和为 $2$，因此满足条件。

输出如 2 4 5 和 4 1 5 也同样被接受。

对于第二组测试数据，图 $G$ 的任意一棵生成树的边权之和都不可能为 $1$。

约束条件

• $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$ 或 $c_i=1$。
• 图 $G$ 是简单图且连通。
• 所有测试数据中 $N$ 的总和不超过 $2\times 10^5$。
• 所有测试数据中 $M$ 的总和不超过 $2\times 10^5$。
• 所有输入值均为整数。