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 翻译