Fişierul intrare/ieşire:tric.in, tric.outSursăONI 2007, clasele 11-12
AutorStefan CiobacaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.125 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 A1 este prieten cu A2, A2 cu A3, ..., Ak-1 cu Ak si Ak cu A1, atunci exista cel putin o pereche (i, j), 1 ≤ i, j ≤ k, astfel incat:
    • Ai si Aj 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

tric.intric.out
4 4
0 1
1 2
2 0
2 3
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content