Nangijala

시간 제한2초메모리 제한1024 MB

요약

모든 사람이 세계 1에서 시작하고, 한 명을 다음 세계로 보낼 때마다 죽음 하나가 발생한다. 적끼리 같은 세계에 있지 않도록 하는 최소 사망 수를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 그리디, DFS
정답자: 아직 제출이 없습니다

문제

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$

예제3

예제 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
```