Enemy Division

It is the year 2147 and a great war rages across the world. Captain Keram's soldiers have fought side by side since the war began two years ago, and along the way some of them have become enemies of one another. Fortunately, each soldier has at most 3 enemies.

They must soon attack another country, and Keram worries that soldiers who are enemies might not cooperate during battle. He has therefore decided to split the soldiers into groups so that every soldier has at most one of his enemies in his own group. He also wants to keep things simple, so he wants to use as few groups as possible. Help Captain Keram by finding the minimum number of groups he needs.

The first line contains two integers $n$ and $m$ ($2 \le n \le 100,000$, $0 \le m \le 3n/2$), where $n$ is the number of soldiers and $m$ is the number of enemy pairs.

Each of the next $m$ lines contains two space-separated integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$), meaning that soldiers $a_i$ and $b_i$ are enemies. You may assume that every soldier has at most 3 enemies.

Output a single integer: the minimum number of groups $k$ such that the soldiers can be split into $k$ groups with every soldier sharing his group with at most one of his enemies.