Mạng lưới đường phố của Byteburg bao gồm \(n\) giao lộ được liên kết bởi \(m\) đoạn đường hai chiều. Gần đây, Byteburg đã được chọn để tổ chức giải vô địch Duathlon sắp tới. Cuộc thi này bao gồm hai chặng: chặng chạy bộ, tiếp theo là chặng đi xe đạp.

Tuyến đường cho cuộc thi phải được xây dựng theo cách thức sau. Đầu tiên, ba giao lộ phân biệt nhau \(s\), \(c\) và \(f\) được chọn làm điểm xuất phát, chuyển đổi và kết thúc. Sau đó, tuyến đường cho cuộc thi sẽ được xây dựng. Tuyến đường sẽ bắt đầu ở \(s\), đi qua \(c\) và kết thúc ở \(f\). Vì lý do an toàn, tuyến đường chỉ qua mỗi giao lộ nhiều nhất một lần.

Trước khi xây dựng tuyến đường, thị trưởng muốn tính toán số cách để chọn giao lộ \(s\), \(c\) và \(f\) để có thể xây dựng tuyến đường thỏa mãn. Hãy giúp ông ta tính ra số này.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(n\) và \(m\): là số giao lộ và số đoạn đường. Tiếp theo là \(m\) dòng chứa mô tả các đoạn đường (\(1 \le n \le 10^5\), \(1 \le m \le 2 \cdot 10^5\)). Mỗi đoạn đường được mô tả bằng cặp hai số nguyên \(v_i\), \(u_i\), chỉ hai giao lộ có đoạn đường liên kết (\(1 \le v_i, u_i \le n\), \(v_i \ne u_i\)). Giữa mỗi cặp giao lộ, có tối đa một đường nối chúng.

Dữ liệu ra

Ghi ra số cách để chọn các giao lộ \(s\), \(c\) và \(f\) làm điểm xuất phát, chuyển đổi và kết thúc, để có thể xây dựng tuyến đường thỏa mãn cho cuộc thi.

Phân nhóm

Ví dụ

4 3
1 2
2 3
3 4

8

4 4
1 2
2 3
3 4
4 2

14

Giải thích

Trong ví dụ thứ nhất có 8 cách để chọn bộ ba \((s, c, f)\): \((1, 2, 3)\), \((1, 2, 4)\), \((1, 3, 4)\), \((2, 3, 4)\), \((3, 2, 1)\), \((4, 2, 1)\), \((4, 3, 1)\), \((4, 3, 2)\).

Trong ví dụ thứ hai có 14 cách để chọn bộ ba \((s, c, f)\): \((1, 2, 3)\), \((1, 2, 4)\), \((1, 3, 4)\), \((1, 4, 3)\), \((2, 3, 4)\), \((2, 4, 3)\), \((3, 2, 1)\), \((3, 2, 4)\), \((3, 4, 1)\), \((3, 4, 2)\), \((4, 2, 1)\), \((4, 2, 3)\), \((4, 3, 1)\), \((4, 3, 2)\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2018, được lưu trong kho đề APIO.