This problem is identical to "Immoral Graph (Easy)" except for the constraints on $N$ and $M$.

In the world of graphs, two vertices that have never spoken to each other can share the same child.

In a directed acyclic graph, three distinct vertices $x, y, z$ are said to have an "immoral relationship" if they satisfy all of the following conditions:

• There exist edges from $x$ to $z$ and from $y$ to $z$.
• There is no edge connecting $x$ and $y$.

In the graph world, such relationships are considered quite interesting structures.

Given a directed acyclic graph with $N$ vertices and $M$ edges, find the number of immoral relationships.

Input

The first line contains two space-separated integers $N$ and $M$, representing the number of vertices and the number of edges, respectively. $(3\leq N\leq 50\,000;$ $1\leq M\leq 50\,000)$

The next $M$ lines each contain two space-separated integers $u$ and $v$, representing a directed edge from vertex $u$ to vertex $v$. $(1\leq u,v\leq N)$

The given graph is a directed acyclic graph.

All numbers provided in the input are integers.

Output

Output the number of immoral relationships present in the given graph.

Examples

Input 1

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

Output 1

3