← 返回题目列表

AtCoder · kupc2021_e

E. 佩姆斯特

中文机器翻译题面 查看原题

配点 : 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) 。