34690번 - A Graph of Fire and Ice (Hard)

이 문제는 $N$, $M$ 제한을 제외하면 A Graph of Fire and Ice (Easy) 문제와 동일한 문제이다.

$1$부터 $N$까지 번호가 붙은 $N$개의 정점과, $M$개의 간선으로 구성된 연결 무방향 그래프가 주어진다. 각 간선에는 $1$ 이상 $M$ 이하의 서로 다른 정수 가중치가 하나씩 할당되어 있다.

그래프 $G$가 다음 두 조건을 만족할 때, $G$를 얼불 그래프라 한다.

• $G$는 연결 그래프이다.
• $G$의 각 정점에 불 또는 얼음의 속성을 부여하여, 같은 속성의 정점들끼리 연결된 간선의 개수가 최대 $1$개가 되도록 색칠할 수 있다.

대곽이는 주어진 그래프에서 일부 간선을 제거하여, 남은 그래프가 얼불 그래프가 되도록 만들고자 한다. 단, 간선을 제거할 때는 다음의 규칙을 따라야 한다.

• 가중치가 $x$인 간선을 제거하기 위해서는 가중치가 $x$보다 작은 모든 간선을 먼저 제거해야 한다.
• 간선을 제거하는 과정에서 그래프는 항상 연결 그래프로 유지되어야 한다.

제거해야 하는 간선의 최소 개수를 구해 보자.

첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(2\le N\le 250\,000;$ $1\le M\le 500\,000)$

다음 $M$개의 줄의 $i$번째 줄에는 $i$번째 간선이 연결하는 두 정점의 번호 $u_i$, $v_i$와 $i$번 간선의 가중치 $r_i$가 공백으로 구분되어 주어진다. $(1\le u_i,v_i\le N;$ $1\le r_i\le M;$ $u_i \ne v_i)$

서로 다른 간선의 가중치가 동일한 경우는 없으며, 하나의 정점 쌍을 연결하는 간선은 최대 $1$개 존재한다.

제거해야 하는 간선의 최소 개수를 출력한다. 만약 불가능하다면 -1을 출력한다.