Contar el número de triángulos en un grafo
Dado un grafo no dirigido con v vértices y e aristas, se te pide calcular cuántos triángulos hay en el grafo.
Un triángulo en un grafo es un conjunto de 3 vértices que están todos conectados entre sí.
Por ejemplo, el grafo de la imagen contiene 3 triángulos:
1-2-5
2-5-4
3-2-4
Entrada
La primera línea de la entrada contiene dos números enteros v (1 ≤ v ≤ 100) y e (1 ≤ e ≤ ).
Las siguientes e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que indican que el vértice v1 está conectado con el vértice v2 y viceversa.
Salida
El programa debe imprimir el número de triángulos en el grafo dado.
Ejemplos
Entrada | Salida |
|---|---|
5 7 | 3 |
3 2 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB