TriunghiuriGraf

Cerință

Se dă un graf neorientat cu $N$ noduri numerotate de la $1$ la $N$ cu $M$ muchii. Se numește triunghi un triplet de noduri $(x, y, z)$ astfel încât există muchie între oricare aceste noduri. Să se numere câte triunghiuri există în acest graf.

Date de intrare

Din fișierul de intrare triunghiuri.in, pe prima linie se citesc numerele $N$ și $M$. Urmează $M$ linii, fiecare conținând două numere reprezentând muchiile grafului.

Date de ieșire

În fișierul de ieșire triunghiuri.out, se va găsi, pe prima linie, numărul de triunghiuri determinat.

Restricții și precizări

• Subtask $1$ ($17$p): $1 \leq N \leq 300$
• Subtask $2$ ($29$p): $1 \leq N \leq 1000$, $1 \leq M \leq 10000$
• Subtask $3$ ($18$p): $1 \leq N \leq 100000$, $1 \leq M \leq 1000$
• Subtask $4$ ($17$p): $1 \leq N \leq 100000$, $1 \leq M \leq 50000$
• Subtask $5$ ($19$p): $1 \leq N, M \leq 100000$

Exemple

triunghiuri.in

9 9
1 2
1 3
2 3
3 4
4 5
5 6
5 7
6 7
7 8

triunghiuri.out

2

Explicație

Cele $2$ triunghiuri sunt formate de către tripletele $(1, 2, 3)$, respectiv $(5, 6, 7)$.