Six Words

이 문제의 원래 제목은 “Line Line Graph Minimum Spanning Tree”이다.

이 문제에서는 단순 연결 무방향 그래프를 다룬다. 모든 간선 $e$에는 가중치 $w(e)$가 있고, 모든 정점 $v$에는 포텐셜 $p(v)$가 있다.

그래프 $G$의 라인 그래프 $L(G)$는 $G$의 간선 사이의 인접 관계를 나타내는 그래프이다. 형식적으로, $L(G)$의 각 정점은 $G$의 간선 하나에 대응하고, $L(G)$의 두 정점은 $G$에서 대응하는 두 간선이 공통 끝점을 가질 때, 그리고 그럴 때만 인접하다.

$L(G)$의 각 정점의 포텐셜은 $G$에서 대응하는 간선의 가중치와 같다. $L(G)$의 각 간선 $e$의 가중치는 $e$의 양 끝점에 대응하는 $G$의 두 간선이 공유하는 $G$의 끝점 정점의 포텐셜과 같다.

$G$가 연결 그래프이면 $L(G)$도 연결 그래프이다.

그래프의 최소 신장 트리 (MST)는 모든 정점을 연결하면서 사이클이 없고 간선 가중치 합이 최소인 간선 부분집합이다.

$n$개의 정점과 $m$개의 간선을 가진 그래프 $G$가 주어진다. 정점은 $1$부터 $n$까지 번호가 매겨져 있고, $G$의 정점 $i$의 포텐셜은 $i$이다. 간선은 $1$부터 $m$까지 번호가 매겨져 있고, $G$의 간선 $i$의 가중치는 $i$이다.

$L(L(G))$의 최소 신장 트리의 간선 가중치 합을 구하여라.

첫 번째 줄에는 두 정수 $n$과 $m$이 주어진다. ($3 \le n \le 10^5$; $2 \le m \le \min(n(n-1)/2, 2 \cdot 10^5)$) 이는 $G$의 정점 수와 간선 수이다.

다음 $m$개의 줄에는 각각 두 정수 $u_i$와 $v_i$가 주어진다. ($1 \le u_i, v_i \le n$; $u_i \ne v_i$) 이는 $i$번째 간선의 양 끝점이다.

두 정점 사이에는 간선이 최대 하나만 존재한다. 그래프는 연결 그래프이다.

$G$의 라인 그래프의 라인 그래프의 최소 신장 트리의 간선 가중치 합을 출력한다.

첫 번째 예제에서 $L(L(G)) = G$이고, $G$의 MST의 간선 가중치 합은 $1 + 2 = 3$이다.