부도덕한 그래프 (Hard)

이 문제는 부도덕한 그래프 (Easy)와 $N$과 $M$의 제한을 제외하면 동일한 문제입니다.

그래프 세계에선 서로 말 한마디 섞어본 적 없는 두 정점이 같은 자식을 갖기도 한다.

사이클 없는 단순 방향 그래프의 서로 다른 정점 $x, y, z$가 다음 조건을 모두 만족하면 이를 부도덕한 관계라고 한다.

• $x$에서 $z$로 가는 간선과 $y$에서 $z$로 가는 간선이 모두 존재한다.
• $x$와 $y$를 잇는 간선이 없다.

그래프 세계에선 이런 관계가 꽤 흥미로운 구조로 취급된다.

$N$개의 정점과 $M$개의 간선으로 이루어진 사이클 없는 단순 방향 그래프가 주어진다. 부도덕한 관계의 개수를 구해 보자.

첫째 줄에 정점의 수 $N$과 간선의 수 $M$이 공백으로 구분되어 주어진다. $(3\leq N\leq 50\,000;$ $1\leq M\leq 50\,000)$

둘째 줄부터 $M$개의 줄에 걸쳐 간선을 나타내는 두 정수 $u, v$가 공백으로 구분되어 주어진다. 이는 정점 $u$에서 정점 $v$로 향하는 간선을 의미한다. $(1\leq u,v\leq N)$

주어진 그래프는 사이클 없는 단순 방향 그래프이다.

입력으로 주어지는 모든 수는 정수이다.

주어진 그래프에 존재하는 부도덕한 관계의 수를 출력한다.