Эта задача идентична задаче «Аморальный граф (Easy)», за исключением ограничений на $N$ и $M$.

В мире графов случается так, что две вершины, которые никогда не общались друг с другом, имеют общего «ребенка».

В простом ориентированном ациклическом графе три различные вершины $x, y, z$ образуют «аморальное отношение», если выполняются следующие условия:

• Существуют ребра из $x$ в $z$ и из $y$ в $z$.
• Между $x$ и $y$ нет прямого ребра.

В мире графов такие отношения считаются довольно интересной структурой.

Дан простой ориентированный ациклический граф с $N$ вершинами и $M$ ребрами. Найдите количество аморальных отношений.

Входные данные

В первой строке через пробел заданы количество вершин $N$ и количество ребер $M$. $(3\leq N\leq 50\,000;$ $1\leq M\leq 50\,000)$

В следующих $M$ строках заданы два целых числа $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