스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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 ≤ a_i, b_i < N, a_i ≠ 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 ≤ 100000, varje människa har som mest en fiende |
| 2 | 36 | N ≤ 100000, varje människa har som mest två fiender |
| 3 | 26 | N ≤ 10, grafen av fiender är ett träd |
| 4 | 27 | N ≤ 100000, grafen av fiender är ett träd |
예제
예제 1
5 2 0 1 3 4
2
예제 2
5 4 0 1 1 2 2 0 3 4
4
예제 3
8 7 0 1 0 2 0 3 1 4 1 5 1 6 1 7
3