Runda 3: Kaktus

Limit czasu: 5s,  limit pamięci: 64MB

Prędzej mi kaktus na dłoni wyrośnie, niż podejmę się takiego zadania! - zawołał Witek. Chłopcy po zakończeniu eksperymentu z mrówkami zajęli się analizą grafów (nieskierowanych). Witkowi w przydziale zadań przypadł obowiązek liczenia, ile różnych cykli (prostych, czyli bez powtarzających się wierzchołków) znajduje się w zadanym grafie. Witek uważa to zadanie za zdecydowanie zbyt pracochłonne i stąd jego okrzyk protestu.

Po pewnym czasie chłopcom udało się dojść do porozumienia - zadanie Witka pozostanie wprawdzie niezmienione, ale chłopcy ograniczą się do badania grafów w których policzyć cykle powinno być stosunkowo łatwo. A dokładniej do takich grafów, w których dowolne dwa różne cykle mają co najwyżej jeden wspólny wierzchołek.

Pomóż Witkowi w wykonywaniu jego pracy. Jeżeli okaże się, że zadany graf nie spełnia założenia, odmów wykonania zadania.

Wejście

W pierwszej linii znajduje się jedna liczba naturalna L, oznaczająca liczbę zestawów danych. Następnie następuje opis kolejnych zestawów.

W pierwszej linii opisu znajdują się dwie liczby naturalne N i M (1<= N,M <= 1000000), oznaczające - odpowiednio - liczbę wierzchołków i liczbę krawędzi grafu. Następnie podawany jest opis krawędzi grafu w M kolejnych liniach. Każda z nich zawiera dwie różne liczby naturalne A i B oznaczające wierzchołki, które łączy dana krawędź (numerowane od 0). Krawędzie będą parami różne.

Wyjście

Dla każdego zestawu w osobnej linii należy wypisać liczbę cykli w grafie, jeśli ten spełnia opisane w treści założenie, lub "NIE" w przeciwnym przypadku.

Przykład