Boomerangs

Time limit2sMemory limit512 MB

Summary

Count pairs of adjacent edges in a connected graph whose removal disconnects the graph.

Level: Medium7 of 10
Topics: Graph, DFS, Implementation, Brute force
Solved: No attempts yet

Problem

You are given a graph $G$ . $G$ consists of $N$ vertices and $M$ edges and is connected. There are no self-loops, and no two edges share the same pair of endpoints.

If there exist vertices $u, v, w$ such that there is an edge between $u$ and $v$ and an edge between $v$ and $w$ , this pair of edges is called a boomerang.

Find the number of boomerangs such that removing the two edges of the boomerang leaves at least one pair of vertices that cannot reach each other along any sequence of edges.

Input

The first line gives $N$ and $M$ . ( $1 \le N, M \le 5\times10^5$ )

The next $M$ lines give edge information as $u$ and $v$ , meaning there is an edge between vertex $u$ and vertex $v$ . ( $1 \le u, v \le N$ , $u \ne v$ )

Output

Print the number of boomerangs whose removal increases the number of connected components.

Examples1

Example 1
Input
```
6 7
1 2
2 3
3 6
2 4
4 5
1 6
2 5
```
Expected output
```
7
```