Comet OJ

C0479 [APIO2018-C]铁人两项

内存限制：1024 MB 时间限制：1000 ms

题目描述

比特镇的路网由 $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≤v_i,u_i≤n,v_i \ne 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)。

【子任务】（comet 不支持APIO评分方式）

  • Subtask 1 (测试点 3-37，points:5)：$n≤10,m≤100$
  • Subtask 2 (测试点 38-67，points:11)：$n≤50,m≤100$
  • Subtask 3 (测试点 68-89，points:8)：$n≤100000$，每个交叉路口至多作为两条双向道路的端点
  • Subtask 4 (测试点 90-109，points:10)：$n≤1000$，在路网中不存在环（存在环是指存在一个长度为 $k(k≥3)$ 的交叉路口序列 $v_1,v_2,...,v_k$​，序列中的路口编号两两不同，且对于 $i$ 从 $1$ 到 $k−1$，有一条双向道路直接连接路口 $v_i$ ​和 $v_{i+1}$​，且有一条双向道路直接连接路口 $v_k$​ 和 $v_1$​）
  • Subtask 5 (测试点 110-129，points:13)：$n≤100000$，在路网中不存在环
  • Subtask 6 (测试点 130-156，points:15)：$n≤1000$，对于每个交叉路口，至多被一个环包含
  • Subtask 7 (测试点 157-183，points:20)：$n≤100000$，对于每个交叉路口，至多被一个环包含
  • Subtask 8 (测试点 184-210，points:8)：$n≤1000,m≤2000$
  • Subtask 9 (测试点 211-233，points:10)：$n≤100000,m≤200000$