적대 병사 그룹 나누기

시간 제한1초메모리 제한128 MB

요약

각 병사의 적이 최대 3명일 때, 모든 병사가 자기 그룹에서 적과 최대 한 명만 함께하도록 최소 개수의 그룹으로 나눈다.

난이도: 어려움10점 중 8점
유형: 그래프, 그리디, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

2147년, 세계는 큰 전쟁을 겪고 있습니다. 케람 대위의 병사들은 2년 전 전쟁이 시작된 이래로 줄곧 함께 싸워 왔고, 그 사이 일부 병사는 서로 적대 관계가 되었습니다. 다행히 각 병사가 두고 있는 적은 최대 3명뿐입니다.

곧 다른 나라를 공격해야 하는데, 케람 대위는 서로 적인 병사들이 전투 중에 제대로 협력하지 못할까 봐 걱정입니다. 그래서 그는 병사들을 여러 그룹으로 나누되, 모든 병사가 자신이 속한 그룹 안에서는 최대 한 명의 적하고만 같은 그룹이 되도록 하기로 했습니다. 또한 되도록 단순하게 하고 싶어서, 사용하는 그룹의 수를 최소로 하려고 합니다. 케람 대위를 도와, 필요한 그룹의 최소 개수를 구해 주세요.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어집니다 ( $2 \le n \le 100\,000$ , $0 \le m \le 3n/2$ ). 여기서 $n$ 은 병사의 수, $m$ 은 적대 관계인 병사 쌍의 수입니다.

이어지는 $m$ 개의 줄에는 각각 공백으로 구분된 두 정수 $a_i$ 와 $b_i$ 가 주어지며 ( $1 \le a_i < b_i \le n$ ), 이는 병사 $a_i$ 와 병사 $b_i$ 가 서로 적임을 뜻합니다. 모든 병사는 최대 3명의 적을 가진다고 가정할 수 있습니다.

출력

필요한 그룹의 최소 개수 $k$ 를 정수 하나로 출력합니다. 즉, 모든 병사가 자신의 그룹 안에서 최대 한 명의 적하고만 같은 그룹이 되도록 병사들을 나눌 때 필요한 그룹의 최소 개수입니다.

예제3

예제 1
입력
```
4 4
1 2
2 3
3 4
1 4
```
예상 출력
```
2
```
예제 2
입력
```
2 0
```
예상 출력
```
1
```
예제 3
입력
```
2 1
1 2
```
예상 출력
```
1
```