Bus Lines

In Byteotia there are $n$ cities connected by two-way roads, with many villages lying along those roads. King Byteasar has decided to create a network of bus lines serving the cities and villages. Each line may start and end in any city and may pass through any cities. A line may visit the same city more than once. However, no line may travel along the same road more than once.

To provide transport for all residents while keeping the investment cost as low as possible, the king decided that every road must be covered by exactly one bus line, and that the number of bus lines must be as small as possible.

In other words, partition all roads into a set of lines so that each road belongs to exactly one line, and make the number of lines as small as possible. A single line is a walk that never repeats a road (a trail); it may pass through the same city several times.

The first line contains two integers $n$ and $m$ separated by a single space ($2 \le n \le 10000$, $n - 1 \le m \le 200000$), where $n$ is the number of cities and $m$ is the number of roads. Cities are numbered from $1$ to $n$. Each of the next $m$ lines describes one road and contains two integers $a$ and $b$ separated by a single space ($1 \le a < b \le n$), the numbers of the two cities connected by that road. Each road appears in the input exactly once. Any two cities are directly connected by at most one road (although there may be many routes between two cities), and it is possible to travel between any two cities along the roads (the graph is connected).

Output a single line containing one integer $c$, the minimum number of bus lines needed.