20900번 - 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, \dots. 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.

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.

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

• $N \le 100\,000$