AT_kupc2021_e.PERMST

有一个包含 $N$ 个顶点、$M$ 条边的无向简单连通图 $G$。$G$ 的顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

给定一个长度为 $M$ 的只包含 $0$ 和 $1$ 的数列 $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)$ 中，输出字典序最小的一个：

• 若将第 $i$ 条边的权值设为 $p_i$，则 $G$ 的最小生成树所用的所有边都是红色的。
• 此时，$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)$ 中字典序最小的一个，格式如下，末尾需换行。

不得包含多余的空格或除末尾外的换行。（2021年10月31日 14:21 补充）

$p_1$ $p_2$ $\ldots$ $p_M$

限制条件

• $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\}$
• $\{ \text{边 } i \mid c_i = 1 \}$ 构成 $G$ 的一棵生成树。

样例解释 1

当 $P = (3, 1, 4, 5, 2)$ 时，将第 $i$ 条边的权值设为 $P_i$，此时最小生成树所用的所有边都是红色的。$P = (4, 1, 2, 5, 3)$ 也满足条件，但字典序最小的是 $(3, 1, 4, 5, 2)$。

由 ChatGPT 4.1 翻译