적대 병사 그룹 나누기

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