This problem is identical to Immoral Graph (Hard) 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 world of graphs, 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 integers $N$ and $M$, separated by a space, representing the number of vertices and the number of edges, respectively. $(3\leq N\leq 2\,000;$ $1\leq M\leq 4\,000)$

From the second line, $M$ lines follow, each containing two integers $u$ and $v$ separated by a space, 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