Bài toán này giống hệt với bài Đồ thị vô đạo đức (Easy), 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ỳ kết nối nào với nhau vẫn có thể có chung một đứa con.

Xét một đồ thị có hướng 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 không chu trình gồm $N$ đỉnh và $M$ cạnh. Hãy tính số lượng mối quan hệ vô đạo đức trong đồ thị.

Dữ liệu vào

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

$M$ dòng tiếp theo, mỗi 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 không chu trình.

Tất cả các số trong dữ liệu vào đều là số nguyên.

Dữ liệu ra

In ra số lượng 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