King Bajtur, the ruler of Byteland, likes to dream about conquering Bitland. It is pleasant to dream about defeating an opponent, but life is not a dream, and in reality, the situation looks a bit different.

Byteland consists of $n$ cities (numbered from $1$ to $n$) connected by $m$ bidirectional roads. Each road connects two different cities, but it may happen that multiple roads connect the same pair of cities. It is possible to travel from any city to any other city, possibly using multiple roads.

The king wonders what would happen if Bitland attacked Byteland and destroyed three of the $m$ existing roads. What are the chances that this would seriously damage communication in the country? Your task is to determine this! Count how many triples of roads exist such that after their destruction, there will be at least one pair of cities between which it will not be possible to travel using the remaining roads.

Input

The first line of input contains two integers $n$ and $m$ ($2 \le n \le 200\,000$, $3 \le m \le 500\,000$) representing the number of cities and the number of roads in Byteland, respectively.

The next $m$ lines contain descriptions of the roads; the $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) meaning that the $i$-th road connects cities numbered $a_i$ and $b_i$.

You may assume that the road network allows travel from any city to any other city.

Output

The output should contain a single integer equal to the number of such unordered triples of roads that after their removal, there will exist at least two cities between which it will not be possible to travel.

Examples

Input 1

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

Output 1

103

Note

Explanation of the example: Note that after removing, for example, the third, fifth, and seventh roads, Byteland will split into more than two parts. Even so, such a triple of edges should be counted only once.