Contar o Número de Triângulos num Grafo
Dado um grafo não direcionado com
v vértices e e arestas, pretende-se determinar o número de triângulos presentes nesse grafo.Um triângulo num grafo é um conjunto de 3 vértices interligados entre si.
Por exemplo, o grafo apresentado na imagem contém 3 triângulos:
- 1-2-5
- 2-5-4
- 3-2-4
Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 100) e e (1 ≤ e ≤ ).As
e linhas seguintes contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), o que significa que o vértice v1 está ligado ao vértice v2 e vice-versa.Saída
O programa deve imprimir o número de triângulos no grafo fornecido.
Exemplos
Entrada | Saída |
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