Ce problème est identique à « 부도덕한 그래프 (Easy) » à l'exception des contraintes sur $N$ et $M$.

Dans le monde des graphes, deux sommets qui ne se sont jamais parlé peuvent avoir le même enfant.

Dans un graphe orienté simple sans cycle, trois sommets distincts $x, y$ et $z$ forment une relation immorale s'ils satisfont aux conditions suivantes :

• Il existe une arête de $x$ vers $z$ et une arête de $y$ vers $z$.
• Il n'existe aucune arête reliant $x$ et $y$.

Dans le monde des graphes, ce type de relation est considéré comme une structure assez intéressante.

Étant donné un graphe orienté simple sans cycle composé de $N$ sommets et $M$ arêtes, calculez le nombre de relations immorales.

Entrée

La première ligne contient deux entiers $N$ et $M$ séparés par un espace, représentant le nombre de sommets et le nombre d'arêtes. $(3\leq N\leq 50\,000;$ $1\leq M\leq 50\,000)$

Les $M$ lignes suivantes contiennent chacune deux entiers $u$ et $v$ séparés par un espace, représentant une arête dirigée du sommet $u$ vers le sommet $v$. $(1\leq u,v\leq N)$

Le graphe donné est un graphe orienté simple sans cycle.

Tous les nombres fournis en entrée sont des entiers.

Sortie

Affichez le nombre de relations immorales présentes dans le graphe donné.

Exemples

Entrée 1

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

Sortie 1

3