Zadanie w systemie SPOJ (trudne) 497. Trójkąty Jednobarwne Kod zadania: TROJEDNO

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 (1≤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 (3 ≤ n ≤ 1 000), oznaczjąca liczbę punktów w przestrzeni. W drugim wierszu każdego zestawu danych znajduje się liczba całkowita m (0 ≤ m ≤ 25 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, 1≤p≤q≤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:	Rafał Nowak
Data dodania:	2005-03-12
Limit czasu wykonania programu:	2s
Limit długości kodu źródłowego	5000B
Języki programowania:	All except: BF CLPS LISP sbcl LISP clisp ERL HASK ICON ICK JS LUA PHP PIKE PRLG PYTH 2.5 RUBY SCM qobi SCM guile WSPC
Pochodzenie:	Olimpiada Informatyczna