시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 17 9 8 50.000%

문제

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 ui and vi (1 ≤ ui, vi ≤ N). It describes a bidirectional edge connecting vertex ui and vertex vi.

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.

예제 입력 1

3 2
1 2
2 3

예제 출력 1

1

예제 입력 2

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

예제 출력 2

3

예제 입력 3

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

예제 출력 3

0

예제 입력 4

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

예제 출력 4

2

출처