P9105 [PA 2020] Trzy drogi

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Trzy drogi](https://sio2.mimuw.edu.pl/c/pa-2020-1/trz/)** Byteur 国王，Byteotia 的统治者，梦想着征服 Bitotia。梦见打败敌人是件令人愉快的事，然而生活不是一场梦，醒来后情况就有些不同。 Byteotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $m$ 条双向道路连接。每条路都连接着两个不同的城市，但也可能有多条道路连接着同一对城市的情况。从任何城市出发，经过一条或多条道路可以到达其他任意城市。 国王想知道，如果 Bitotia 进攻 Byteotia，从现有的 $m$ 条道路中毁掉三条，会发生什么，将严重损害该国的通信的可能性有多大？你的任务是找出答案！数一数有多少条这样的三条路，在这些路被毁之后，至少有一对城市不可以通过剩余的道路互相到达对方。

第一行包含两个整数 $n,m$，分别表示 Byteotia 的城市个数和道路条数。 接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示城市 $a_i$ 和 $b_i$ 之间被一条道路连接。 你可以假设从任何城市出发，经过一条或多条道路可以到达其他任意城市。

输出一行一个整数，表示移除这三条路，至少存在两个城市彼此不可达的无序三元组的个数。

#### 样例 1 解释  请注意，例如移除第 $3,5,7$ 条路后，Byteotia 会被分为多于两部分，但这样的三元组只能被计算一次。 ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，保证 $2\le n\le 2\times 10^5$，$3\le m\le 5\times 10^5$，$1\le a_i,b_i\le n$，$a_i\neq b_i$。