W Bajtocji wcielane jest w życie przedsięwzięcie polegające na budowie autostrad. Ponieważ skarbiec Bajtocji zaczyna świecić pustkami władze państwa podjęły decyzję że budowa części autostrad powinna zostać odłożona na późniejszy, bliżej nieokreślony, termin. Autostrady mają umożliwić przejazd pojazdów które nie mogą jeździć po zwykłych drogach. Władze Bajtocji chcą zrezygnować z budowy tylko tych autostrad, których wykreślenie nie uniemożliwi przejazdu między miastami, które miały być połączone bezpośrednią autostradą.
Poproszono Cię o pomoc w wyznaczeniu liczby autostrad, które przy przytoczonym kryterium wyboru, trzeba będzie wybudować. Żeby ułatwić Twoje zadanie, udostępniono Ci listę planowanych autostrad, uszeregowanych pod względem ważności. Jeżeli kolejna autostrada z listy miałaby połączyć miasta które są już połączone przez sieć wcześniejszych autostrad, to taka autostrada ma zostać wykreślona.
Pomóż władzom Bajtocji. Napisz program, który wyznaczy liczbę niezbędnych autostrad.
W pierwszym wierszu wejścia znajduje się jedna liczba
naturalna niemniejsza niż 1, określająca liczbę zestawów danych, które za chwilę
pojawią się na wejściu.
W pierwszym wierszu zestawu znajdują się dwie liczby naturalne N i M (2 <= N <= 10000, 1 <= M <= 250000).
N określa liczbę miast. M określa liczbę planowanych autostrad.
W każdym z kolejnych M wierszy znajduje się jedna para liczb z zakresu 1..N, opisująca kolejną autostradę.
Autostradę identyfikują numery miast, jakie ma połączyć.
Dla każdego zestawu danych musisz wypisać liczbę autostrad, które ostatecznie będzie trzeba zbudować.
Dla wejścia:
3 3 4 1 2 2 1 2 3 3 1 2 1 1 2 6 4 3 2 1 6 4 1 6 4poprawnym rozwiązaniem jest:
2 1 3