Jaehyun đã giải một bài toán về lát cắt cực đại của đồ thị tại trại hè Petrozavodsk Winter 2019, vì vậy anh ấy quyết định mang đến cho những người tham gia trại huấn luyện Petrozavodsk một bài toán khác có cùng bản chất.

Bạn được cho một đồ thị đơn liên thông $G = (V, E)$ với $N$ đỉnh và $M$ cạnh. Hãy tìm số lượng các tập con cạnh $S \subseteq E$ sao cho:

• Việc loại bỏ các cạnh trong $S$ làm cho đồ thị trở thành đồ thị hai phía.
• $|S| \le 2$.
• Không tồn tại tập con $T \subseteq E$ nào khác sao cho $|T| < |S|$ và thỏa mãn hai điều kiện đầu tiên.

Lưu ý rằng $S$ có thể là tập rỗng.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $N$ và $M$ ($3 \le N \le 250\,000$, $N - 1 \le M \le 250\,000$).

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách $u_i$ và $v_i$ ($1 \le u_i, v_i \le N$). Mỗi dòng mô tả một cạnh vô hướng nối giữa đỉnh $u_i$ và đỉnh $v_i$.

Đảm bảo rằng đồ thị đã cho không có khuyên hoặc đa cạnh, và đồ thị là liên thông.

Dữ liệu ra

In ra số lượng các tập con cạnh thỏa mãn các điều kiện đã cho.

Ví dụ

Dữ liệu vào 1

3 2
1 2
2 3

Dữ liệu ra 1

1

Dữ liệu vào 2

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

Dữ liệu ra 2

3

Dữ liệu vào 3

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

Dữ liệu ra 3

0

Dữ liệu vào 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

Dữ liệu ra 4

2