增量最小生成森林

【题目描述】

给定一张有 $N$ 个顶点、$0$ 条边的带权无向图，按顺序插入 $M$ 条边 $e_i = (u_i,v_i,w_i)$，并维护该图的最小生成森林（MSF）。注意，由于约束条件，MSF 是唯一的。

设 $F_{-1}$ 为含 $0$ 条边的森林，$F_i$ 为加入边 $e_i$ 之后的 MSF。可以证明以下两种情况之一必然成立。

• $F_{i}=F_{i-1}+e_i$
• $F_{i}=(F_{i-1}+e_i)\setminus e_j$，其中 $j$ 为某个下标。

第一种情况输出 $-1$，第二种情况输出 $j$。

【输入】

$N$ $M$
$u_0$ $v_0$ $w_0$
$u_1$ $v_1$ $w_1$
:
$u_{M - 1}$ $v_{M - 1}$ $w_{M - 1}$

【输出】

$ans_0$ $ans_1$ $ans_2$ ... $ans_{M - 1}$

【输入样例】

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

【输出样例】

-1 -1 1 3 4 

【数据范围】

• $1 \leq N \leq 500000$
• $1 \leq M \leq 1000000$
• $1 \leq w_i \leq 1000000000$
• 所有 $w_i$ 互不相同

【来源】

Library Checker（yosupo06） incremental_minimum_spanning_forest