Kapitan Mamlaków postanowił zaatakować siedzibę kapitana Mambeksa. Uznał,
że najważniejsze dla zwycięstwa będzie zacząć atak od uszkodzenia łączności
w siedzibie kapitana Mambeksa. Siedziba kapitana Mambeksa składa się z wielu
gwiezdnych budynków komunikujących się miedzy sobą kierunkowymi falami
radiowymi tak, że komunikacja między oddalonymi budynkami odbywa się przy
pomocy pośredniej komunikacji innych budynków położonych bliżej. Naukowcy
kapitana Mamlaków wynaleźli urządzenie potrafiące bardzo dobrze zakłucić
łączność radiową jednak na krótkiej odległości (praktycznie potrafi odłączyć
komunikacje jednego budynku). Niestety kapitan posiada na razie tylko jeden
prototypowy model więc zatrudnił Ciebie byś obliczył ile jest takich miejsc
w których postawienie urządzenia spowodowałoby brak komunikacji pomiędzy
chociaż dwoma gwiezdnymi budynkami (nie wliczając tego objętego zakłucającym
urządzeniem), oraz wyznaczył te miejsca. Później kapitan będzie się
zastanawiał gdzie jest najkorzystniej umieścić urządzenie.
Dane wejściowe:
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych. W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. Każdy zestaw składa się z :
N, M: 0 < N <= 100 - liczba budynków, 0 < M <= 10000 - liczba
połączeń radiowych ( max 100 na budynek )
M linii zawierających połączenia x y ( x różne od y oraz x <= N i y
<= N )
Dane wyjściowe
Dla każdego zestawu danych wejściowych program ma wypisać w kolejnych
wierszach:
Liczbę takich miejsc w których postawienie urządzenia spowodowałoby brak
komunikacji pomiędzy chociaż dwoma gwiezdnymi budynkami.
Miejsca ( budynki ) w których można postawić urządzenie, posortowane w kolejności rosnącej.
Pusta linia
Przykładowe dane wejściowe:
1
10 4
1 2
3 2
4 2
5 4
Przykładowe dane wyjściowe:
2
2 4