C - K Spanning Tree 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

N 頂点 M 辺の単純連結無向グラフ G が与えられます。辺 i は頂点 a_i と頂点 b_i を結ぶ重み c_i の辺です。ここで、各辺の重みは 0 または 1 です。

非負整数 K が与えられます。G の全域木であって、その全域木を構成する辺の重みの和がちょうど K であるものが存在するかを判定し、存在するなら一つ求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 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 以下
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

T 行出力せよ。i 行目には \text{case}_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} の並び順は自由である。辺番号は各ケース内での入力順に対応する。解が複数存在する場合は、どれを出力しても正解とみなされる。

入力例 1

2
4 5 2
1 2 0
1 3 0
2 3 0
4 2 1
4 3 1
4 4 1
1 2 1
2 3 1
2 4 1
3 4 0

出力例 1

1 4 5
-1

1 つ目のケースについて、辺 1,4,5 から構成されるグラフは G の全域木となっており、また辺の重みの和が 2 であるため、条件を満たします。

2 4 5、 4 1 5 などの出力も正解となります。

2 つ目のケースについて、グラフ G の全域木の辺の重みの和を 1 にすることはできません。

Score : 600 points

Problem Statement

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.

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.

Input

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

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 Input 1

2
4 5 2
1 2 0
1 3 0
2 3 0
4 2 1
4 3 1
4 4 1
1 2 1
2 3 1
2 4 1
3 4 0

Sample Output 1

1 4 5
-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.