Problem C
Nangijala

I Astrid Lindgrens roman Bröderna Lejonhjärta kommer man till Nangijala efter döden. Om man dör i Nangijala kommer man till Nangilima. I Nangilima kan man inte dö och alla lever i harmoni, men man skulle kunna tänka sig att det finns fler världar bortom Nangilima.

I det här problemet finns det oändligt många världar numrerade 1, 2, 3, …. Alla människor finns ursprungligen i värld 1 och när någon dör i värld $i$ kommer hen till värld $i+1$.

Just nu finns det $N$ människor i värld 1. Bland dessa människor finns det $M$ par av fiender. Fiender ogillar varandra så mycket att de helst skulle vilja befinna sig i olika världar. Fiendeskap är en symmetrisk relation vilket innebär att om person $a$ är en fiende till person $b$ så är också $b$ en fiende till $a$.

Avgör minsta antalet dödsfall som krävs för att ingen människa ska befinna sig i samma värld som någon av sina fiender.

Indata

Den första raden innehåller de positiva heltalen $N$ och $M$. Sedan följer $M$ rader med heltal $a_ i$, $b_ i$ $(0 \le a_ i, b_ i < N, a_ i \neq b_ i)$ som betyder att $a_ i$ och $b_ i$ är fiender.

Utdata

Skriv ut ett enda tal – minsta antalet dödsfall som behövs för att inga fiender ska finnas i samma värld.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

5 2
0 1
3 4

2

5 4
0 1
1 2
2 0
3 4

4

8 7
0 1
0 2
0 3
1 4
1 5
1 6
1 7

3