問題文

N 頂点 M 辺の無向単純連結グラフ G があります。 G の頂点には 1 から N までの番号がついていて、辺には 1 から M までの番号がついています。 G の辺 i は頂点 u_i と頂点 v_i を結んでいます。

0 および 1 からなる長さ M の数列 C = (c_1, c_2, \ldots, c_M) が与えられます。 c_i が 0 のとき辺 i は青色で塗られていて、c_i が 1 のとき辺 i は赤色で塗られています。 ここで、c_i = 1 となる i はちょうど N-1 個あり、赤色の辺は G の全域木をなしています。

次の条件を満たす、1 から M までの整数を並び替えた順列 P = (p_1, p_2, \ldots, p_M) のうち、辞書順最小のものを求めてください。

• G の辺 i の重みを p_i とすると、G の最小全域木に使われている辺はすべて赤色である。
• このとき、G の最小全域木は一意に定まることに注意せよ。

制約

• 2 \le N \le 2 \times 10^5
• N - 1 \le M \le 2 \times 10^5
• 1 \le u_i < v_i \le N
• 1 \leq i < j \leq M に対して (u_i, v_i) \neq (u_j, v_j)
• c_i \in \{0, 1\}
• \{辺 i \mid c_i = 1\} は G の全域木をなしている。

入力例1

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

出力例1

3 1 4 5 2

P = (3, 1, 4, 5, 2) とすると、辺 i の重みを P_i としたときの最小全域木に使われている辺はすべて赤色になります。 P = (4, 1, 2, 5, 3) としてもこの条件は満たされますが、P のうち辞書順で最も小さいものは (3, 1, 4, 5, 2) です。