题目描述

题目译自 PA 2020 Runda 5 Trzy drogi

Byteur 国王，Byteotia 的统治者，梦想着征服 Bitotia。梦见打败敌人是件令人愉快的事，然而生活不是一场梦，醒来后情况就有些不同。

Byteotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $m$ 条双向道路连接。每条路都连接着两个不同的城市，但也可能有多条道路连接着同一对城市的情况。从任何城市出发，经过一条或多条道路可以到达其他任意城市。

国王想知道，如果 Bitotia 进攻 Byteotia，从现有的 $m$ 条道路中毁掉三条，会发生什么，将严重损害该国的通信的可能性有多大？你的任务是找出答案！数一数有多少条这样的三条路，在这些路被毁之后，至少有一对城市不可以通过剩余的道路互相到达对方。

输入格式

第一行包含两个整数 $n,m\ (2\le n\le 2\cdot 10^5,3\le m\le 5\cdot 10^5)$，分别表示 Byteotia 的城市个数和道路条数。

接下来 $m$ 行，每行两个整数 $a_i,b_i\ (1\le a_i,b_i\le n,a_i\neq b_i)$，表示城市 $a_i$ 和 $b_i$ 之间被一条道路连接。

你可以假设从任何城市出发，经过一条或多条道路可以到达其他任意城市。

输出格式

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

8 11
2 3
4 5
3 1
3 2
5 7
3 6
1 2
3 4
6 5
8 7
7 8

103