Fişierul intrare/ieşire:	tric.in, tric.out	Sursă	ONI 2007, clasele 11-12
Autor	Stefan Ciobaca	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.125 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tric

Din cei n participanti la olimpiada de informatica se pot distinge m perechi de prieteni. Aceste perechi au cateva proprietati interesante:

• daca A este prieten cu B, atunci B este prieten cu A;
• daca A₁ este prieten cu A₂, A₂ cu A₃, ..., A_k-1 cu A_k si A_k cu A₁, atunci exista cel putin o pereche (i, j), 1 ≤ i, j ≤ k, astfel incat:
  • A_i si A_j sunt prieteni
  • (i mod k) + 1 ≠ j
  • (j mod k) + 1 ≠ i

Se numeste triunghi de prieteni un set de 3 prieteni A, B si C, cu proprietatea ca A este prieten cu B, B cu C si C cu A.

Cerinta

Aflati cate triunghiuri de prieteni exista.

Date de intrare

Pe prima linie a fisierului de intrare tric.in se gasesc, separate prin spatii, numerele naturale n si m. Pe urmatoarele m linii se gasesc perechi de numere A B, intre 0 si n-1, cu semnificatia ca A este prieten cu B.

Date de iesire

Pe singura linie a fisierului de iesire tric.out afisati numarul de triunghiuri de prieteni.

Restrictii

• 2 ≤ n ≤ 100 000
• 1 ≤ m ≤ 100 000
• pentru 20% din teste, n ≤ 300
• pentru 50% din teste, n ≤ 1000

Exemplu

Cum se trimit solutii?