Koosaga's problem

Time limit2sMemory limit1024 MB

Summary

Count the edge subsets of size at most two that make the connected graph bipartite, where no smaller removal set also works.

Level: Hard8 of 10
Topics: Graph, BFS, Combinatorics
Solved: No attempts yet

Problem

Jaehyun solved a problem about the maximum cut of a graph at the Petrozavodsk Winter 2019 camp, so he decided to give you another problem of the same nature.

You are given a simple connected graph $G = (V, E)$ with $N$ vertices and $M$ edges. Find the number of edge subsets $S \subseteq E$ that satisfy the following:

Removing the edges in $S$ makes the graph bipartite.
$|S| \le 2$ .
No other subset $T \subseteq E$ with $|T| < |S|$ satisfies the first two conditions.

Note that $S$ can be empty.

Input

The first line contains two integers $N$ and $M$ ( $3 \le N \le 250000$ , $N-1 \le M \le 250000$ ).

Each of the next $M$ lines contains two space-separated integers $u_i$ and $v_i$ ( $1 \le u_i, v_i \le N$ ), describing an edge between vertex $u_i$ and vertex $v_i$ .

The graph has no loops or multiple edges, and it is connected.

Output

Print the number of edge subsets that satisfy the conditions above.

Examples4

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

Example 3

Input

Expected output

Example 4

Input

Expected output