この問題は、「不道徳なグラフ (Easy)」と $N$ および $M$ の制約を除いて同一の問題です。

グラフの世界では、互いに言葉を交わしたことのない2つの頂点が同じ子を持つことがある。

サイクルを持たない単純有向グラフにおいて、異なる3つの頂点 $x, y, z$ が以下の条件をすべて満たすとき、これを不道徳な関係と呼ぶ。

• $x$ から $z$ への辺と $y$ から $z$ への辺が両方存在する。
• $x$ と $y$ を結ぶ辺が存在しない。

グラフの世界では、このような関係は非常に興味深い構造として扱われる。

$N$ 個の頂点と $M$ 個の辺からなる、サイクルを持たない単純有向グラフが与えられる。不道徳な関係の個数を求めよ。

入力

1行目に頂点の数 $N$ と辺の数 $M$ が空白区切りで与えられる。 $(3\leq N\leq 50\,000;$ $1\leq M\leq 50\,000)$

2行目から $M$ 行にわたって、辺を表す2つの整数 $u, v$ が空白区切りで与えられる。これは頂点 $u$ から頂点 $v$ へ向かう辺を意味する。 $(1\leq u,v\leq N)$

与えられるグラフはサイクルを持たない単純有向グラフである。

入力されるすべての数は整数である。

出力

与えられたグラフに存在する不道徳な関係の個数を出力せよ。

入出力例

入力 1

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

出力 1

3