B. Koosaga's Problem
time limit per test
2 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Jaehyun solved a problem about the maximum cut of graph at Petrozavodsk Winter 2019 camp, so he decided to please the participants of Petrozavodsk training camp with 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 subsets of edges $$$S \subseteq E$$$ such that:

  • The removal of edges in $$$S$$$ makes the graph bipartite.
  • $$$|S| \le 2$$$.
  • There exists no other subset $$$T \subseteq E$$$ such that $$$|T| \lt |S|$$$ and the first two conditions hold.

Note that $$$S$$$ can be empty.

Input

The first line of the input contains two integers $$$N$$$ and $$$M$$$ ($$$3 \le N \le 250\,000$$$, $$$N - 1 \le M \le 250\,000$$$).

Then $$$M$$$ lines follow. Each of them contains two space-separated integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le N$$$). It describes a bidirectional edge connecting vertex $$$u_i$$$ and vertex $$$v_i$$$.

It is guaranteed that the given graph doesn't have any loops or multiple edges, and the graph is connected.

Output

Print the number of subsets of edges that satisfy the given conditions.

Examples
Input
3 2
1 2
2 3
Output
1
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Output
3
Input
5 9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
Output
0
Input
12 16
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 5
1 5
2 7
3 9
4 11
Output
2