==Include(page="template/taskheader" task_id="color")==
 
==Include(page="template/raw")==
 
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).
 
h2. Cerinta
 
Scrieti un program care sa determine pentru un graf colorat dat numarul de triunghiuri monocromatice.
 
h2. Date de Intrare:
 
Fisierul de intrare color.in contine:
 
color.in ]Semnificatie
N S N - numarul de varfuri din graf , S - numarul de muchii rosii
 
x[1] y[1 x[i] y[i] - extrmitatile celei de a i muchii rosii
 
]x[2] y[2
 
]...
 
x[S] y[S
 
h2. Date de Iesire:
 
Fisierul de iesire color.out contine pe prima linie numarul de triunghiuri monocromatice.
 
h2. Restrictii si precizari
 
S 1 <= N <= 4.000
 
S 1 <= S <= 500.000
 
S In fisierul de intrare nu apare de mai multe ori aceeasi muchie.
 
S Muchiile care nu apar in fisierul de intrare sunt colorate, evident, in negru.
 
h2. Exemplu
 
color.in color.out
4 4 1
 
1 2
 
2 3
 
4 3
 
4 2
 

==Include(page="template/taskheader" task_id="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).
 
h2. Cerinta
 
Scrieti un program care sa determine pentru un graf colorat dat numarul de triunghiuri monocromatice.
 
h2. Date de Intrare
 
Fisierul de intrare $color.in$ contine:
 
table(example). | N S
 x{~1~} y{~1~}
 x{~2~} y{~2~}
 ...
 x{~s~} y{~s~}
| N - numarul de varfuri din graf, S - numarul de muchii rosii
 x{~i~} y{~i~} - extrmitatile celei de a i-a muchii rosii |
 
h2. Date de Iesire
 
Fisierul de iesire $color.out$ contine pe prima linie numarul de triunghiuri monocromatice.
 
h2. 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.
 
h2. Exemplu
 
table(example). |_. color.in |_. color.out |
| 4 4
1 2
2 3
4 3
4 2
| 1 |
 
==Include(page="template/taskfooter" task_id="color")==

==Include(page="template/taskfooter" task_id="color")==

463