점진적 최소 스패닝 포리스트

$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$
• 어떤 $j$에 대해 $F_{i}=(F_{i-1}+e_i)\setminus e_j$.

첫 번째 경우에는 $-1$를 출력하고, 두 번째 경우에는 $j$를 출력한다.

제약 조건

• $1 \leq N \leq 500000$
• $1 \leq M \leq 1000000$
• $1 \leq w_i \leq 1000000000$
• 모든 $w_i$는 서로 다르다

$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}$