.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » tric

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
tric


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
64MB / 1MB

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

Exemple

tric.intric.out
4 4 0 1 1 2 2 0 2 3 1

autor: Ştefan Ciobâcă
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor