Problem Description

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

King Byteur, the ruler of Byteotia, dreams of conquering Bitotia. Dreaming of defeating the enemy is pleasant, but life is not a dream, and after waking up things look a bit different.

Byteotia consists of $n$ cities (numbered from $1$ to $n$) connected by $m$ undirected roads. Each road connects two different cities, but there may be multiple roads connecting the same pair of cities. From any city, it is possible to reach any other city by traveling along one or more roads.

The king wants to know: if Bitotia attacks Byteotia and destroys three of the existing $m$ roads, how likely is it that the country’s communication will be seriously damaged? Your task is to find the answer. Count how many triples of roads have the property that, after these roads are destroyed, there exists at least one pair of cities that cannot reach each other using the remaining roads.

Input Format

The first line contains two integers $n, m$, representing the number of cities and the number of roads in Byteotia.

The next $m$ lines each contain two integers $a_i, b_i$, indicating that there is a road connecting city $a_i$ and city $b_i$.

You may assume that from any city, it is possible to reach any other city by traveling along one or more roads.

Output Format

Output one line with one integer: the number of unordered triples of roads such that after removing these three roads, there exist at least two cities that are not reachable from each other.

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

Hint

Explanation of Sample 1

Note that, for example, after removing roads $3, 5, 7$, Byteotia will be split into more than two parts, but such a triple is counted only once.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $2 \le n \le 2 \times 10^5$, $3 \le m \le 5 \times 10^5$, $1 \le a_i, b_i \le n$, and $a_i \neq b_i$.

Translated by ChatGPT 5