Условие недоступно на русском языке
K2. 부도덕한 그래프 (Hard)
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

이 문제는 부도덕한 그래프 (Easy)와 N과 M의 제한을 제외하면 동일한 문제입니다.

그래프 세계에선 서로 말 한마디 섞어본 적 없는 두 정점이 같은 자식을 갖기도 한다.

사이클 없는 단순 방향 그래프의 서로 다른 정점 x, y, z가 다음 조건을 모두 만족하면 이를 부도덕한 관계라고 한다.

  • x에서 z로 가는 간선과 y에서 z로 가는 간선이 모두 존재한다.
  • x와 y를 잇는 간선이 없다.

그래프 세계에선 이런 관계가 꽤 흥미로운 구조로 취급된다.

N개의 정점과 M개의 간선으로 이루어진 사이클 없는 단순 방향 그래프가 주어진다. 부도덕한 관계의 개수를 구해 보자.

Input

첫째 줄에 정점의 수 N과 간선의 수 M이 공백으로 구분되어 주어진다. (3 ≤ N ≤ 50 000; 1 ≤ M ≤ 50 000)

둘째 줄부터 M개의 줄에 걸쳐 간선을 나타내는 두 정수 u, v가 공백으로 구분되어 주어진다. 이는 정점 u에서 정점 v로 향하는 간선을 의미한다. (1 ≤ u, v ≤ N)

주어진 그래프는 사이클 없는 단순 방향 그래프이다.

입력으로 주어지는 모든 수는 정수이다.

Output

주어진 그래프에 존재하는 부도덕한 관계의 수를 출력한다.

Example
Input
6 6
2 3
3 1
2 1
2 6
5 6
4 6
Output
3