19862번 - Koosaga's problem 다국어

Jaehyun solved a problem about the maximum cut of graph at Petrozavodsk Winter 2019 camp, so he decided to please you 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 ⊆ E such that:

• The removal of edges in S makes the graph bipartite.
• |S| ≤ 2.
• There exists no other subset T ⊆ E such that |T| < |S| and the first two conditions hold. Note that S can be empty.

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

Then M lines follow. Each of them contains two space-separated integers u_i and v_i (1 ≤ u_i, v_i ≤ 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.

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