Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TROJEDNO - Trójkąty Jednobarwne

Zadanie: Trójkąty jednobarwne


W przestrzeni rozmieszczono n punktów w taki sposób, że żadne trzy z nich nie są współliniowe. Następnie każdą parę tych punktów połączono odcinkiem i każdy odcinek pokolorowano na czaro albo na czerwono. Trójkątem jednobarwnym nazwiemy każdy trójkąt mający wszystkie trzy boki tego samego koloru. Mamy daną listę wszystkich czerwonych odcinków. Chcemy znaleźć liczbę wszystkich trójkątów jednobarwnych.

Zadanie
Napisz program, który:

  • wczyta ze standardowego wejścia: liczbę punktów, liczbę odcinków czerwonych oraz ich listę
  • znajdzie liczbę trójkątów jednobarwnych,
  • wypisze wynik na standardowe wyjście.

Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowia D (≤ ≤ 10), oznaczjąca liczbę przypadków do rozważenia. Opis każdego przypadku podany jest w następujący sposób: w jego pierwszym wierszu zapisana jest liczba całkowita n (3n ≤ 1 000), oznaczjąca liczbę punktów w przestrzeni. W drugim wierszu każdego zestawu danych znajduje się liczba całkowita m (0 ≤ m ≤ 86 000), oznaczająca liczbę czerwonych odcinków. W następnych m wierszach znajdują się opisy tych odcinków (w każdym wierszu opis czerwonego odcinka podany jest poprzez dwie liczby całkowite p i q oddzielone pojedynczym odstępem, 1pq≤n).

Wyjście
Dla każdego przypadku z wejścia Twój program powinien wypisać (w osobnej linii dla każdego przypadku z wejścia) liczbę trójkątów jednobarwnych

Przykład
Dla danych wejściowych:

2
6
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6
4
2
1 2
1 3

poprawną odpowiedzią jest:

2
1

Dodane przez:Rafal Nowak
Data dodania:2005-03-12
Limit czasu wykonania programu:2s
Limit długości kodu źródłowego5000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Olimpiada Informatyczna

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.