재현이는 Petrozavodsk Winter 2019 캠프에서 그래프의 최대 컷(maximum cut)에 관한 문제를 해결했고, 이번에는 같은 성격의 또 다른 문제로 Petrozavodsk 훈련 캠프 참가자들을 즐겁게 해주기로 했습니다.

$N$개의 정점과 $M$개의 간선을 가진 단순 연결 그래프 $G = (V, E)$가 주어집니다. 다음 조건을 만족하는 간선들의 부분집합 $S \subseteq E$의 개수를 구하세요.

• $S$에 속한 간선들을 제거하면 그래프는 이분 그래프(bipartite)가 됩니다.
• $|S| \le 2$.
• $|T| < |S|$이면서 첫 번째와 두 번째 조건을 만족하는 다른 부분집합 $T \subseteq E$는 존재하지 않습니다.

$S$는 공집합일 수 있음에 유의하세요.

입력

첫 번째 줄에는 두 정수 $N$과 $M$ ($3 \le N \le 250\,000$, $N - 1 \le M \le 250\,000$)이 주어집니다.

그다음 $M$개의 줄이 이어집니다. 각 줄에는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le N$)가 공백으로 구분되어 주어지며, 이는 정점 $u_i$와 정점 $v_i$를 잇는 양방향 간선을 의미합니다.

주어진 그래프에는 루프나 다중 간선이 없으며, 그래프는 연결되어 있음이 보장됩니다.

출력

주어진 조건을 만족하는 간선 부분집합의 개수를 출력하세요.

예제

입력 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