To zadanie jest identyczne z zadaniem "부도덕한 그래프 (Easy)", z wyjątkiem ograniczeń na $N$ i $M$.

W świecie grafów zdarza się, że dwa wierzchołki, które nigdy ze sobą nie rozmawiały, mają tego samego potomka.

W skierowanym grafie acyklicznym (DAG) trzy różne wierzchołki $x, y, z$ tworzą tzw. relację niemoralną, jeśli spełnione są następujące warunki:

• Istnieją krawędzie z $x$ do $z$ oraz z $y$ do $z$.
• Nie istnieje krawędź łącząca $x$ i $y$.

W świecie grafów takie relacje uznaje się za dość interesującą strukturę.

Dany jest skierowany graf acykliczny o $N$ wierzchołkach i $M$ krawędziach. Oblicz liczbę relacji niemoralnych w tym grafie.

W pierwszej linii podano dwie liczby całkowite $N$ oraz $M$, oddzielone spacją, oznaczające odpowiednio liczbę wierzchołków i liczbę krawędzi. $(3\leq N\leq 50\,000;$ $1\leq M\leq 50\,000)$

W kolejnych $M$ liniach podano po dwie liczby całkowite $u, v$, oddzielone spacją, oznaczające krawędź skierowaną z wierzchołka $u$ do wierzchołka $v$. $(1\leq u,v\leq N)$

Podany graf jest skierowanym grafem acyklicznym.

Wszystkie liczby podane na wejściu są liczbami całkowitymi.

Wypisz liczbę relacji niemoralnych występujących w podanym grafie.

Przykład

Wejście 1

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

Wyjście 1

3