[APIO2018] Duathlon 铁人两项

题目描述

比特镇的路网由 $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

输出样例 #1

8

输入样例 #2

4 4
1 2
2 3
3 4
4 2

输出样例 #2

14

说明

**提示** 在第一个样例中,有以下 $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)$。 在第二个样例中,有以下 $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)$。 **子任务(注:这里给出的子任务与本题在这里的最终评测无关,仅供参考)** - Subtask 1(points: $5$):$n \leq 10$,$m \leq 100$。 - Subtask 2(points: $11$):$n \leq 50$,$m \leq 100$。 - Subtask 3(points: $8$):$n \leq 100000$,每个交叉路口至多作为两条双向道路的端点。 - Subtask 4(points: $10$):$n \leq 1000$,在路网中不存在环(存在环是指存在一个长度为 $k$($k \ge 3$)的交叉路口序列 $v_1, v_2, \ldots, v_k$,序列中的路口编号两两不同,且对于 $i$ 从 $1$ 到 $k - 1$,有一条双向道路直接连接路口 $v_i$ 和 $v_{i+1}$,且有一条双向道路直接连接路口 $v_k$ 和 $v_1$)。 - Subtask 5(points: $13$):$n \leq 100000$,在路网中不存在环。 - Subtask 6(points: $15$):$n \leq 1000$,对于每个交叉路口,至多被一个环包含。 - Subtask 7(points: $20$):$n \leq 100000$,对于每个交叉路口,至多被一个环包含。 - Subtask 8(points: $8$):$n \leq 1000$,$m \leq 2000$。 - Subtask 9(points: $10$):$n \leq 100000$,$m \leq 200000$。