题目描述

比特镇的路网由 $m$ 条双向道路连接的 $n$ 个交叉路口组成。

最近，比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程：选手先完成一段长跑赛程，然后骑自行车完成第二段赛程。

比赛的路线要按照如下方法规划：

1. 先选择三个两两互不相同的路口 $s$，$c$ 和 $f$ ，分别作为比赛的起点、切换点（运动员在长跑到达这个点后，骑自行车前往终点）、终点。
2. 选择一条从 $s$ 出发，经过 $c$ 最终到达 $f$ 的路径。考虑到安全因素，选择的路径经过同一个点至多一次。

在规划路径之前，镇长想请你帮忙计算，总共有多少种不同的选取 $s$，$c$ 和 $f$ 的方案，使得在第 2 步中至少能设计出一条满足要求的路径。

输入格式

第一行包含两个整数 $n$ 和 $m$ ，分别表示交叉路口和双向道路的数量。

接下来 $m$ 行，每行两个整数 $v_i$，$u_i$ 。表示存在一条双向道路连接交叉路口 $v_i$，$u_i$（$1 \le v_i, u_i \le n$，$v_i \neq u_i$）。

保证任意两个交叉路口之间，至多被一条双向道路直接连接。

输出格式

输出一行，包括一个整数，表示能满足要求的不同的选取 $s$，$c$ 和 $f$ 的方案数。

样例 1

输入

4 3
1 2
2 3
3 4

输出

8

说明

在第一个样例中，有以下 $8$ 种不同的选择 $(s, c, f)$ 的方案：$(1, 2, 3)$，$(1, 2, 4)$，$(1, 3, 4)$，$(2, 3, 4)$，$(3, 2, 1)$，$(4, 2, 1)$，$(4, 3, 1)$，$(4, 3, 2)$。

样例 2

输入

4 4
1 2
2 3
3 4
4 2

输出

14

说明

在第二个样例中，有以下 $14$ 种不同的选择 $(s, c, f)$ 的方案：$(1, 2, 3)$，$(1, 2, 4)$，$(1, 3, 4)$，$(1, 4, 3)$，$(2, 3, 4)$，$(2, 4, 3)$，$(3, 2, 1)$，$(3, 2, 4)$，$(3, 4, 1)$，$(3, 4, 2)$，$(4, 2, 1)$，$(4, 2, 3)$，$(4, 3, 1)$，$(4, 3, 2)$。

数据范围与提示

• 子任务 1（$5$ 分）：$n \le 10$，$m \le 100$
• 子任务 2（$11$ 分）：$n \le 50$，$m \le 100$
• 子任务 3（$8$ 分）：$n \le 100000$，每个交叉路口至多作为两条双向道路的端点。
• 子任务 4（$10$ 分）：$n \le 1000$，在路网中不存在环。
• 子任务 5（$13$ 分）：$n \le 100000$，在路网中不存在环。
• 子任务 6（$15$ 分）：$n \le 1000$，对于每个交叉路口，至多被一个环包含。
• 子任务 7（$20$ 分）：$n \le 100000$，对于每个交叉路口，至多被一个环包含。
• 子任务 8（$8$ 分）：$n \le 1000$，$m \le 2000$
• 子任务 9（$10$ 分）：$n \le 100000$，$m \le 200000$