시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 73 8 8 21.622%

문제

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

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

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

입력

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

출력

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

예제 입력

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

예제 출력

4

힌트

출처