107. 铁人三项

单点时限: 1.0 sec

内存限制: 1024 MB

子任务测试。

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

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

输出格式

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

样例

Input
4 3
1 2
2 3
3 4
Output
8
Input
4 4
1 2
2 3
3 4
4 2
Output
14

提示

子任务分值分布见:https://loj.ac/problem/2587

1 人解决,2 人已尝试。

2 份提交通过,共有 6 份提交。

9.7 EMB 奖励。

创建: 2 年,3 月前.

修改: 1 年,4 月前.

最后提交: 2 年,1 月前.

来源: APIO 2018

题目标签