408086: GYM102984 B Koosaga's Problem

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| < |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 \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.

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

3 2
1 2
2 3

1

4 6
1 2
1 3
1 4
2 3
2 4
3 4

3

5 9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5

0

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

2