AlgoLiga 2018

Bitazarowi, po sukcesach w rozwożeniu pizzy (tu i tu), wreszcie udało się uzbierać wystarczająco dużo pieniędzy na założenie własnej sieci pizzerii. Nie stać go na razie na to, aby w każdym mieście znajdowała się jego restauracja, więc postanowił zoptymalizować nieco proces ich budowania. Wymyślił następujące kryterium: niech każde z N miast Bajtogrodu zawiera jego pizzerię lub znajduje się w bezpośrednim sąsiedztwie z miastem które taką pizzerię posiada. W ten sposób zasięg jego sieci będzie w pewnym sensie bardzo daleki. Pytanie zatem - ile minimalnie restauracji musi zbudować?

Wejście

Nieokreślona ilość zestawów danych. Każdy zestaw danych to para liczb naturalnych: 1 ≤ N ≤ 35, M oznaczających kolejno liczbę miast Bajtogrodu oraz liczbę połączeń między nimi. Potem następuje M par liczb 1 ≤ a,b ≤ N opisujących te połączenia. Jedna taka para oznacza, że pomiędzy miastami o numerach a oraz b istnieje połączenie (są w bezpośrednim sąsiedztwie). Wejście kończy para (N,M) = (0,0).

Uwaga: pomiędzy dwoma miastami może istnieć wiele połączeń oraz mogą istnieć drogi zaczynające i kończące się w tym samym mieście (tzn a = b).

Wyjście

Dla każdego testu w oddzielnej linii odpowiedź na postawione w treści zadania pytanie.

Przykład

Wejście:
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0

Wyjście:
2


Wyjaśnienie do przykładu: 
W tym przypadku z jedną pizzerią nie da się spełnić kryterium Bitazara.
Możemy je jednak spełnić stawiając restauracje na przykład w miastach: 4 oraz 6.