다이아몬드

시간 제한2초메모리 제한1024 MB

요약

하나의 간선을 공유하는 삼각형 두 개로 이루어진 다이아몬드의 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 그래프, 조합론
정답자: 아직 제출이 없습니다

문제

고대 잉카의 책에 페니와이즈를 물리치는 방법이 적혀 있다는 사실을 알게 되었습니다. 이 책을 찾았지만, 안타깝게도 그래프의 언어로 쓰여 있습니다.

이 책의 한 페이지를 이해하려면, 그 페이지에 그려진 그래프에 있는 다이아몬드의 개수를 세어야 합니다.

자기 루프와 다중 간선이 없는 무방향 그래프에서 다이아몬드는 공통된 변을 하나 가지는 두 개의 삼각형을 말합니다.

두 다이아몬드는 한쪽에는 속하지만 다른 쪽에는 속하지 않는 간선이 있으면 서로 다른 것으로 봅니다.

입력

첫째 줄에 정점의 개수 $n$ 과 간선의 개수 $m$ 이 주어집니다 ( $4 \leq n, m \leq 300\,000$ ). 다음 $m$ 개의 줄에는 각각 $i$ 번째 간선이 연결하는 두 정점 $a_i$ , $b_i$ 가 주어집니다 ( $1 \leq a_i, b_i \leq n$ ; $a_i \neq b_i$ ). 주어지는 그래프에는 다중 간선이 없다고 보장됩니다.

출력

그래프에 있는 다이아몬드의 개수를 한 줄에 출력합니다.

예제3

예제 1
입력
```
4 4
1 2
2 3
3 4
4 1
```
예상 출력
```
0
```
예제 2
입력
```
4 5
1 2
2 3
3 4
4 1
1 3
```
예상 출력
```
1
```
예제 3
입력
```
4 6
1 2
2 3
3 4
4 1
1 3
2 4
```
예상 출력
```
6
```