KATT 2017, tävling 2

Start

2017-03-05 09:18 CET

KATT 2017, tävling 2

End

2017-03-05 14:18 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1013 days 2:18:03

Time elapsed

5:00:00

Time remaining

0:00:00

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.

Grupp

Poängvärde

Gränser

1

11

$N \le 100\, 000,$ varje människa har som mest en fiende

2

36

$N \le 100\, 000,$ varje människa har som mest två fiender

3

26

$N \le 10,$ grafen av fiender är ett träd

4

27

$N \le 100\, 000,$ grafen av fiender är ett träd

Sample Input 1 Sample Output 1
5 2
0 1
3 4
2
Sample Input 2 Sample Output 2
5 4
0 1
1 2
2 0
3 4
4
Sample Input 3 Sample Output 3
8 7
0 1
0 2
0 3
1 4
1 5
1 6
1 7
3