Ce problème est identique à « Graphe immoral (Hard) », à 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, z$ forment une relation immorale s'ils satisfont toutes les 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 entre $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 le nombre de sommets $N$ et le nombre d'arêtes $M$, séparés par un espace. $(3\leq N\leq 2\,000;$ $1\leq M\leq 4\,000)$

À partir de la deuxième ligne, $M$ lignes décrivent les arêtes, chacune contenant deux entiers $u, v$ séparés par un espace. Cela signifie qu'il existe une arête allant 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