Enemy Division

Time limit1sMemory limit128 MB

Summary

Divide soldiers into the fewest groups so that each soldier shares a group with at most one enemy, where every soldier has at most 3 enemies.

Level: Hard8 of 10
Topics: Graph, Greedy, Combinatorics, Implementation
Solved: No attempts yet

Problem

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.

Input

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

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.

Examples3

Example 1
Input
```
4 4
1 2
2 3
3 4
1 4
```
Expected output
```
2
```
Example 2
Input
```
2 0
```
Expected output
```
1
```
Example 3
Input
```
2 1
1 2
```
Expected output
```
1
```