Graph

Interview

Time limit2sMemory limit1024 MB

Summary

Count non-adjacent vertex pairs where adding an edge creates exactly one simple cycle, meaning the path between them is unique.

Level: Medium5 of 10
Topics: Graph, DFS, Tree
Solved: No attempts yet

Statement

Many years ago, Alfa was given an undirected graph as a birthday present. Recently, while sorting through his belongings, he found it and was very surprised. After playing with it for a while, he became curious: how many pairs of vertices have no edge between them, such that adding an edge between them creates exactly one new simple cycle (a cycle that visits no vertex twice)?

Input

The first line contains two integers $n, m$ ( $1 \le n, m \le 10^5$ ), the number of vertices and edges in the graph. Each of the next $m$ lines contains a pair of integers $u, v$ ( $1 \le u, v \le n$ ), an edge of the graph.

Output

Print the number of such vertex pairs on a single line.

Examples2

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