Din cei n participanţi la olimpiada de informatică se pot distinge m perechi de prieteni. Aceste perechi au câteva proprietăţi interesante:
- dacă A este prieten cu B, atunci B este prieten cu A;
- dacă A1 este prieten cu A2, A2 cu A3, ..., Ak-1 cu Ak şi Ak cu A1, atunci există cel puţin o pereche (i, j), 1 ≤ i, j ≤ k, astfel încât:
- Ai şi Aj sunt prieteni şi
- (i mod k) + 1 ≠ j şi (j mod k) + 1 ≠ i
Se numeşte triunghi de prieteni un set de 3 prieteni A, B şi C, cu proprietatea că A este prieten cu B, B cu C şi C cu A.
Cerinţă
Aflaţi câte triunghiuri de prieteni există.
Date de intrare
Pe prima linie a fişierului de intrare tric.in se găsesc, separate prin spaţii, numerele naturale n şi m. Pe următoarele m linii se găsesc perechi de numere A B, între 0 şi n – 1, cu semnificaţia că A este prieten cu B.
Date de ieşire
Pe singura linie a fişierului de ieşire tric.out afişaţi numărul de triunghiuri de prieteni.
Restricţii
2 ≤ n ≤ 100 000
1 ≤ m ≤ 100 000
pentru 20% din teste, n ≤ 300
pentru 50% din teste, n ≤ 1000