Zähle die Anzahl der Dreiecke in einem Graphen
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Die Aufgabe besteht darin, die Anzahl der Dreiecke in diesem Graphen zu ermitteln.Ein Dreieck (triangle) in einem Graphen ist eine Gruppe aus drei Knoten, bei der jeder Knoten mit jedem anderen verbunden ist.
Zum Beispiel hat der im Bild gezeigte Graph 3 Dreiecke:
- 1-2-5
- 2-5-4
- 3-2-4
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 100) und e (1 ≤ e ≤ ).Die folgenden
e Zeilen enthalten jeweils zwei ganze Zahlen v1, v2 (1 ≤ v1, v2 ≤ v), was bedeutet, dass der Knoten v1 mit dem Knoten v2 und umgekehrt verbunden ist.Ausgabe
Das Programm soll die Anzahl der Dreiecke in dem gegebenen Graphen ausgeben.
Beispiele
Eingabe | Ausgabe |
5 7
1 2
1 5
2 5
4 5
2 4
2 3
3 4 | 3 |
3 2
1 2
2 3 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB