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
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