Bài toán này giống với bài toán Đồ thị vô đạo đức (Hard) ngoại trừ các giới hạn của $N$ và $M$.

Trong thế giới đồ thị, hai đỉnh chưa từng có bất kỳ mối liên hệ nào với nhau vẫn có thể có chung một đỉnh con.

Trong một đồ thị có hướng đơn không chu trình, ba đỉnh phân biệt $x, y, z$ được gọi là có mối quan hệ vô đạo đức nếu thỏa mãn tất cả các điều kiện sau:

• Tồn tại cạnh từ $x$ đến $z$ và cạnh từ $y$ đến $z$.
• Không tồn tại cạnh nối giữa $x$ và $y$.

Trong thế giới đồ thị, mối quan hệ này được coi là một cấu trúc khá thú vị.

Cho một đồ thị có hướng đơn không chu trình gồm $N$ đỉnh và $M$ cạnh. Hãy tính số lượng các mối quan hệ vô đạo đức.

Dữ liệu vào

Dòng đầu tiên chứa số đỉnh $N$ và số cạnh $M$ cách nhau bởi dấu cách. $(3\leq N\leq 2\,000;$ $1\leq M\leq 4\,000)$

Từ dòng thứ hai trở đi, mỗi dòng trong $M$ dòng chứa hai số nguyên $u, v$ cách nhau bởi dấu cách, biểu thị một cạnh từ đỉnh $u$ đến đỉnh $v$. $(1\leq u,v\leq N)$

Đồ thị đã cho là đồ thị có hướng đơn không chu trình.

Tất cả các số được cung cấp trong đầu vào đều là số nguyên.

Dữ liệu ra

In ra số lượng các mối quan hệ vô đạo đức tồn tại trong đồ thị đã cho.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3