AT_arc225_c [ARC225C] K Spanning Tree

$ N $ 頂点 $ M $ 辺の単純連結無向グラフ $ G $ が与えられます。辺 $ i $ は頂点 $ a_i $ と頂点 $ b_i $ を結ぶ重み $ c_i $ の辺です。ここで、各辺の重みは $ 0 $ または $ 1 $ です。 非負整数 $ K $ が与えられます。 $ G $ の全域木であって、その全域木を構成する辺の重みの和がちょうど $ K $ であるものが存在するかを判定し、存在するなら一つ求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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} $ の並び順は自由である。辺番号は各ケース内での入力順に対応する。解が複数存在する場合は、どれを出力しても正解とみなされる。

### Sample Explanation 1 $ 1 $ つ目のケースについて、辺 $ 1,4,5 $ から構成されるグラフは $ G $ の全域木となっており、また辺の重みの和が $ 2 $ であるため、条件を満たします。 `2 4 5`、 `4 1 5` などの出力も正解となります。 $ 2 $ つ目のケースについて、グラフ $ G $ の全域木の辺の重みの和を $ 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 $ または $ c_i=1 $ - グラフ $ G $ は単純連結である。 - 全てのテストケースにおける $ N $ の総和は $ 2\times 10^5 $ 以下 - 全てのテストケースにおける $ M $ の総和は $ 2\times 10^5 $ 以下 - 入力される値は全て整数