题目描述
比特镇的路网由 m 条双向道路连接的 n 个交叉路口组成。
最近,比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程:选手先完成一段长跑赛程,然后骑自行车完成第二段赛程。
比赛的路线要按照如下方法规划:
- 先选择三个两两互不相同的路口 s,c和 f,分别作为比赛的起点、切换点(运动员在长跑到达这个点后,骑自行车前往终点)、终点。
- 选择一条从 s出发,经过 c最终到达 f的路径。考虑到安全因素,选择的路径经过同一个点至多一次。
在规划路径之前,镇长想请你帮忙计算,总共有多少种不同的选取 s,c和 f的方案,使得在第 2步中至少能设计出一条满足要求的路径。
输入格式
第一行包含两个整数 n和 m ,分别表示交叉路口和双向道路的数量。
接下来 m行,每行两个整数 vi,ui 。表示存在一条双向道路连接交叉路口 vi,ui (1≤vi,ui≤n,vi=ui)。
保证任意两个交叉路口之间,至多被一条双向道路直接连接。
输出格式
输出一行,包括一个整数,表示能满足要求的不同的选取 s,c和 f的方案数。
4 3
1 2
2 3
3 4
8
4 4
1 2
2 3
3 4
4 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≤10,m≤100
- Subtask 2(points: 11): n≤50,m≤100
- Subtask 3(points: 8): n≤100000,每个交叉路口至多作为两条双向道路的端点
- Subtask 4(points: 10): n≤1000,在路网中不存在环(存在环是指存在一个长度为 k(k≥3) 的交叉路口序列 v1,v2,...,vk,序列中的路口编号两两不同,且对于 i从 1到 k−1,有一条双向道路直接连接路口 vi和 vi+1,且有一条双向道路直接连接路口 vk和v1)
- Subtask 5(points: 13): n≤100000,在路网中不存在环
- Subtask 6(points: 15): n≤1000,对于每个交叉路口,至多被一个环包含
- Subtask 7(points: 20): n≤100000,对于每个交叉路口,至多被一个环包含
- Subtask 8(points: 8): n≤1000,m≤2000
- Subtask 9(points: 10): n≤100000,m≤200000