Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 19:57:03.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:color.in, color.outSursăLot 2002
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Color

Consideram un graf complet cu N varfuri in care muchiile sunt colorate fie in rosu, fie in negru. In acest graf se pot forma triunghiuri monocromatice (trei varfuri conectate prin muchii colorate cu aceeasi culoare).

Cerinta

Scrieti un program care sa determine pentru un graf colorat dat numarul de triunghiuri monocromatice.

Date de Intrare

Fisierul de intrare color.in contine:

N S
x1 y1
x2 y2
...
xs ys
N - numarul de varfuri din graf, S - numarul de muchii rosii
xi yi - extrmitatile celei de a i-a muchii rosii

Date de Iesire

Fisierul de iesire color.out contine pe prima linie numarul de triunghiuri monocromatice.

Restrictii si precizari

  • 1 ≤ N ≤ 4.000
  • 1 ≤ S ≤ 500.000
  • In fisierul de intrare nu apare de mai multe ori aceeasi muchie.
  • Muchiile care nu apar in fisierul de intrare sunt colorate, evident, in negru.

Exemplu

color.incolor.out
4 4
1 2
2 3
4 3
4 2
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?