1762번 - 평면그래프와 삼각형

문제

N(1 ≤ N ≤ 100,000)개의 정점으로 이루어진 평면그래프가 있다. 이 평면그래프에 삼각형, 즉 길이가 3인 사이클이 몇 개나 존재하는지 알아내는 프로그램을 작성하시오.

평면그래프란, 열심히 노력하면 간선들이 서로 겹치지 않도록 평면상에 그릴 수 있는 그래프를 말한다.

서로 다른 세 정점 x, y, z가 있을 때, x-y, y-z, z-x의 세 간선이 존재하면 세 정점 x, y, z는 삼각형을 이루고 있다고 한다.

정점은 1번부터 N번까지 번호가 매겨져 있다.

입력

첫째 줄에 두 정수 N, M이 주어진다. M은 간선의 개수를 나타내는 0 이상 300,000 이하의 정수이다. 다음 M개의 줄에는 각 간선이 연결하는 서로 다른 두 정점의 번호가 주어진다. 같은 간선이 중복되어 입력으로 주어지지 않으며, 간선들에는 방향성이 없다.

출력

첫째 줄에 삼각형의 개수를 출력한다.

제한

힌트