POLSKI SPOJ

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 ≤ 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, 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