Three Roads

This problem is translated from PA 2020 Round 5 Trzy drogi.

Byteur, the king of Byteotia, dreams of conquering Bitotia. Although defeating one’s enemies is a delightful notion in dreams, reality is less forgiving.

Byteotia consists of \(n\) cities (numbered from \(1\) to \(n\)) connected by \(m\) bidirectional roads. Each road connects two distinct cities, and there may be multiple roads connecting the same pair of cities. It is guaranteed that from any city one can reach any other city via one or more roads.

The king wonders: if Bitotia attacks and destroys exactly three of the \(m\) roads, how badly will the communication in the country be disrupted? In other words, count the number of ways to choose three roads such that after their removal, there exists at least one pair of cities that becomes disconnected in the remaining network.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(2 \le n \le 10^5\), \(3 \le m \le 3\cdot10^5\)) representing the number of cities and roads.

Each of the following \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le n\), \(u \ne v\)) meaning there is a road connecting city \(u\) and city \(v\). Note that there may be multiple roads between the same pair of cities.

outputFormat

Output a single integer — the number of ways to choose three roads such that, after their removal, there exists at least one pair of cities that becomes disconnected in the remaining graph.

sample

4 4
1 2
2 3
3 4
4 1

0