외계인 납치 2

면접 대비

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

요약

친구 관계 그래프에서 함께 납치해야 하는 연결된 무리의 최대 크기를 구합니다.

난이도: 쉬움10점 중 3점
유형: 그래프, 유니온 파인드, BFS
정답자: 아직 제출이 없습니다

문제

외계인들이 지구를 방문해 여느 때처럼 실험을 위해 사람들을 납치하려고 한다. 과거의 외계인 납치 사건은 언론의 큰 관심을 받았고 여러 억측을 낳았다. 다행히 대부분의 사람들은 이런 이야기를 믿지 않고 외계인이 실제로 존재하지 않는다고 생각한다.

앞으로도 눈에 띄지 않기 위해 은하 인간 포획 위원회(GCPC)가 납치에 관한 규칙을 정했다. 외계인은 납치를 준비할 때 이 규칙을 반드시 따라야 한다. 여러 번 나누어 이동할 수 있지만(외계인의 이동은 매우 빨라서 실제로는 제약이 되지 않는다), 인간에게 비밀이 드러나지 않도록 신중하게 움직여야 한다. 한 사람을 납치하려면 그 사람의 친구를 모두 같은 시간에 함께 납치해야 한다. 그래야 친구와 어울리려고 할 때 아무도 친구가 사라진 것을 알아채지 못한다. 지구의 친구 관계는 양방향이다. 즉 Alice가 Bob의 친구이면 Bob도 Alice의 친구이다.

외계인은 대상을 관찰하며 친구 관계를 모두 기록했다. 친구를 포함해 총 $n$ 명을 납치해야 한다. 외계인은 우주선을 빌리려고 하며, $n$ 명을 모두 납치하려면 우주선에 얼마만큼의 공간이 필요한지 알고 싶어 한다. 우주선의 저장 공간은 동시에 실을 수 있는 사람 수로 잰다. $n$ 명을 모두 납치하는 데 필요한 최소 저장 공간은 얼마인가?

입력

첫 줄에 두 정수 $n$ 과 $m$ 이 주어진다( $1 \leq n \leq 2 \cdot 10^5$ , $0 \leq m \leq 2 \cdot 10^5$ ). $n$ 은 사람의 수이고 $m$ 은 친구 관계의 수이다. 이어지는 $m$ 개의 줄에는 정수 $i$ 와 $j$ 가 주어진다( $1 \leq i < j \leq n$ ). 이는 사람 $i$ 와 사람 $j$ 가 친구라는 뜻이다. 같은 친구 관계는 두 번 이상 주어지지 않는다.

출력

모든 사람을 납치하는 데 필요한 최소 저장 공간을 출력한다.

예제3

예제 1
입력
```
5 3
1 2
2 3
4 5
```
예상 출력
```
3
```
예제 2
입력
```
3 0
```
예상 출력
```
1
```
예제 3
입력
```
8 8
1 2
2 3
3 4
1 4
1 5
2 6
3 7
4 8
```
예상 출력
```
8
```