Este problema es idéntico a "Grafo inmoral (Easy)", excepto por las restricciones de $N$ y $M$.

En el mundo de los grafos, dos vértices que nunca han intercambiado una palabra pueden tener el mismo hijo.

En un grafo dirigido acíclico simple, se dice que tres vértices distintos $x, y, z$ forman una relación inmoral si se cumplen todas las condiciones siguientes:

• Existen aristas desde $x$ hacia $z$ y desde $y$ hacia $z$.
• No existe una arista que conecte $x$ con $y$.

En el mundo de los grafos, este tipo de relación se considera una estructura bastante interesante.

Se te proporciona un grafo dirigido acíclico simple con $N$ vértices y $M$ aristas. Calcula el número de relaciones inmorales.

Entrada

La primera línea contiene el número de vértices $N$ y el número de aristas $M$ separados por un espacio. $(3\leq N\leq 50\,000;$ $1\leq M\leq 50\,000)$

Desde la segunda línea, se proporcionan $M$ líneas, cada una con dos enteros $u, v$ separados por un espacio, que representan una arista. Esto significa que hay una arista dirigida desde el vértice $u$ hacia el vértice $v$. $(1\leq u,v\leq N)$

El grafo proporcionado es un grafo dirigido acíclico simple.

Todos los números proporcionados en la entrada son enteros.

Salida

Imprime el número de relaciones inmorales que existen en el grafo dado.

Ejemplos

Entrada 1

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

Salida 1

3