#2587. 「APIO2018」铁人两项

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zjq

题目描述

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

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

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

1、先选择三个两两互不相同的路口 ssscccfff ,分别作为比赛的起点、切换点(运动员在长跑到达这个点后,骑自行车前往终点)、终点。

2、选择一条从 sss 出发,经过 ccc 最终到达 fff 的路径。考虑到安全因素,选择的路径经过同一个点至多一次。

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

输入格式

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

接下来 mmm 行,每行两个整数 viv_iviuiu_iui 。表示存在一条双向道路连接交叉路口 viv_iviuiu_iui (1≤vi,ui≤n1 \le v_i, u_i \le n1vi,uin, vi≠uiv_i \neq u_ivi̸=ui)。

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

输出格式

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

样例

样例输入1

4 3
1 2
2 3
3 4

样例输出1

8

样例解释1

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

样例输入2

4 4
1 2
2 3
3 4
4 2

样例输出2

14

样例解释2

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

数据范围与提示

子任务 1(5 分):n≤10n \le 10n10, m≤100m \le 100m100

子任务 2(11 分):n≤50n \le 50n50, m≤100m \le 100m100

子任务 3(8 分):n≤100 000n \le 100\,000n100000, 每个交叉路口至多作为两条双向道路的端点。

子任务 4(10 分):n≤1 000n \le 1\,000n1000, 在路网中不存在环。

存在环是指存在一个长度为 kkk (k≥3k\ge 3k3) 的交叉路口序列 v1,v2,…vkv_1, v_2, \ldots v_kv1,v2,vk ,序列中的路口编号两两不同,且对于 iii111k−1k-1k1 ,有一条双向道路直接连接路口 viv_ivivi+1v_{i+1}vi+1 ,且有一条双向道路直接连接路口 vkv_kvkv1v_1v1

子任务 5(13 分):n≤100 000n \le 100\,000n100000, 在路网中不存在环。

子任务 6(15 分):n≤1 000n \le 1\,000n1000, 对于每个交叉路口,至多被一个环包含。

子任务 7(20 分):n≤100 000n \le 100\,000n100000, 对于每个交叉路口,至多被一个环包含。

子任务 8(8 分):n≤1 000n \le 1\,000n1000, m≤2 000m \le 2\,000m2000

子任务 9(10 分):n≤100 000n \le 100\,000n100000, m≤200 000m \le 200\,000m200000