시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
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.
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
Olympiad > Swedish Olympiad in Informatics > 2017 > KATT2 C번