「PA 2020」Trzy drogi

题目描述

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

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

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

输入格式

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

接下来 $m$ 行，每行两个整数 $a_i, b_i$ ($1 \leq a_i, b_i \leq 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

请注意，例如移除第 $3,5,7$ 条路后，Byteotia 会被分为多于两部分，但这样的三元组只能被计算一次。