Problem #158

tric

Time limit: 0.15s
Memory limit: 64MB
Input: tric.in
Output: tric.out

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ă \(A_1\) este prieten cu \(A_1\), \(A_2\) cu \(A_3\), ..., \(A_{k-1}\) cu \(A_k\) şi \(A_k\) cu \(A_1\), atunci există cel puţin o pereche (i, j), 1 ≤ i, j ≤ k, astfel încât: \(A_i\) şi \(A_j\) 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 şi precizări

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

Exemplu

tric.in

4 4
0 1
1 2
2 0
2 3

tric.out

1

General info

Uploader: liviu

Author: Ştefan Ciobâcă

Source: ONI 2007 XI-XII: Ziua 1 Problema 3

Submissions