Compter le nombre de triangles dans un graphe

Étant donné un graphe non orienté avec v sommets et e arêtes, vous devez déterminer le nombre de triangles présents dans ce graphe.

Un triangle dans un graphe est un ensemble de 3 sommets qui sont tous reliés entre eux.

Par exemple, le graphe illustré comporte 3 triangles :

  1. 1-2-5

  2. 2-5-4

  3. 3-2-4

profound.academy-graphs-triangles.drawio.png

Entrée

La première ligne d'entrée contient deux entiers v (1 ≤ v ≤ 100) et e (1 ≤ e ≤ ).

Les e lignes suivantes contiennent des paires d'entiers v1, v2 (1 ≤ v1, v2 ≤ v), indiquant que le sommet v1 est relié au sommet v2 et inversement.

Sortie

Le programme doit afficher le nombre de triangles dans le graphe donné.

Exemples

Entrée

Sortie

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

To check your solution you need to sign in
Sign in to continue