配点 : 300 点
問題文
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 构成了一棵生成树。
入力
输入是按以下格式从标准输入给出的。
N M u_1 v_1 c_1 u_2 v_2 c_2 \vdots u_M v_M c_M
出力
满足条件的排列 P = (p_1, p_2, \ldots, p_M) 中,按字典顺序最小的,请以以下形式输出,并按构成换行。
不得包含多余的空格或除消耗之外的换行。(10/31 14:21 追记)
p_1 p_2 \ldots p_M
入力例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) 。