시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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