在本题中，我们考虑简单的连通无向图。每条边 $e$ 都有权重 $w(e)$。每个顶点 $v$ 都有势能 $p(v)$。

图 $G$ 的线图 $L(G)$ 是另一个表示 $G$ 中边之间邻接关系的图。形式上，$L(G)$ 的每个顶点代表 $G$ 的一条边，当且仅当 $L(G)$ 中的两个顶点所对应的 $G$ 中的边在 $G$ 中共享一个公共端点时，这两个顶点在 $L(G)$ 中相邻。

$L(G)$ 中每个顶点的势能等于其在 $G$ 中对应边的权重。$L(G)$ 中每条边 $e$ 的权重等于 $G$ 中作为 $e$ 对应顶点的公共端点的那个顶点的势能。

注意，只要 $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(\frac{n(n-1)}{2}, 2 \cdot 10^5)$)，分别表示 $G$ 中的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$; $u_i \neq v_i$)，表示第 $i$ 条边的两个端点。

任意两个顶点之间最多只有一条边。图是连通的。

输出格式

输出 $L(L(G))$ 的最小生成树的总边权。

样例

输入格式 1

3 3
1 2
1 3
2 3

输出格式 1

3

说明

在第一个样例测试中，$L(L(G)) = G$，且 $G$ 的 MST 总边权为 $1 + 2 = 3$。

输入格式 2

4 4
2 4
1 3
1 2
4 1

输出格式 2

9