#P4630. [APIO2018] 铁人两项

[APIO2018] 铁人两项

题目描述

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

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

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

  1. 先选择三个两两互不相同的路口 ssccff,分别作为比赛的起点、切换点(运动员在长跑到达这个点后,骑自行车前往终点)、终点。
  2. 选择一条从 ss 出发,经过 cc 最终到达 ff 的路径。考虑到安全因素,选择的路径经过同一个点至多一次。

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

输入格式

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

接下来 mm 行,每行两个整数 vi,uiv_i, u_i。表示存在一条双向道路连接交叉路口 vi,uiv_i, u_i1vi,uin1 \le v_i, u_i \le nviuiv_i \neq u_i)。

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

输出格式

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

4 3
1 2
2 3
3 4

8

4 4
1 2
2 3
3 4
4 2

14

提示

提示

在第一个样例中,有以下 88 种不同的选择 (s,c,f)(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)(4, 2, 1), (4, 3, 1), (4, 3, 2)

在第二个样例中,有以下 1414 种不同的选择 (s,c,f)(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)(4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)

子任务(注:这里给出的子任务与本题在这里的最终评测无关,仅供参考)

  • Subtask 1(points: 55):n10n \leq 10m100m \leq 100
  • Subtask 2(points: 1111):n50n \leq 50m100m \leq 100
  • Subtask 3(points: 88):n100000n \leq 100000,每个交叉路口至多作为两条双向道路的端点。
  • Subtask 4(points: 1010):n1000n \leq 1000,在路网中不存在环(存在环是指存在一个长度为 kkk3k \ge 3)的交叉路口序列 v1,v2,,vkv_1, v_2, \ldots, v_k,序列中的路口编号两两不同,且对于 ii11k1k - 1,有一条双向道路直接连接路口 viv_ivi+1v_{i+1},且有一条双向道路直接连接路口 vkv_kv1v_1)。
  • Subtask 5(points: 1313):n100000n \leq 100000,在路网中不存在环。
  • Subtask 6(points: 1515):n1000n \leq 1000,对于每个交叉路口,至多被一个环包含。
  • Subtask 7(points: 2020):n100000n \leq 100000,对于每个交叉路口,至多被一个环包含。
  • Subtask 8(points: 88):n1000n \leq 1000m2000m \leq 2000
  • Subtask 9(points: 1010):n100000n \leq 100000m200000m \leq 200000