Snow Plows

Time limit3sMemory limit128 MB

Summary

Find the fewest trails that cover every street exactly once by counting odd-degree intersections in each connected part.

Level: Medium4 of 10
Topics: Graph, DFS
Solved: No attempts yet

Problem

The city hall of a certain town does not want to be caught off guard by winter as it is every year, so it is already preparing next year's snow-removal plan.

The heart of the plan is buying modern snow plows. The city hall keeps the plows in garages located at some of the intersections. There is plenty of time to prepare, so a plow can be stationed at any intersection.

When it is time to clear the snow, the plows simply drive along the town's streets. Every street is two-way, but because these plows are very wide, driving through a street once is enough to clear it. After finishing its work, a plow does not have to return to its home intersection; it just pulls into some garage.

Buying the plows is not the whole story: fuel is needed too, and this is exactly where the city hall hopes to save. The fuel spent pulling from an intersection into a garage is negligibly small, so the fuel one plow uses equals the number of streets it drives along. Therefore the total fuel is smallest exactly when every street is driven along exactly once.

Among all plans that use this smallest amount of fuel, how few plows are enough to clear every street?

Input

The first line contains one natural number $Z$ ( $Z = 1$ ), the number of test sets. The test sets follow.

The first line of a test set contains two natural numbers $n$ ( $1 \le n \le 100000$ ) and $m$ ( $1 \le m \le 1000000$ ): the number of intersections and the number of streets, respectively. Each of the next $m$ lines contains two distinct natural numbers $a$ and $b$ ( $1 \le a, b \le n$ ), describing a street connecting intersections $a$ and $b$ . Streets are two-way, and several streets may connect the same pair of intersections.

Output

For each test set, print one line containing a single natural number $L$ : the minimum number of plows for which clearing every street uses the least possible fuel.

The least possible fuel is used exactly when every street is driven along exactly once, so the streets must be split into $L$ routes such that each street belongs to exactly one route and each route is a continuous drive along streets. Output the smallest such $L$ .

Examples3

Example 1
Input
```
1
6 6
1 2
3 2
4 5
1 3
2 3
6 5
```
Expected output
```
2
```
Example 2
Input
```
1
2 1
1 2
```
Expected output
```
1
```
Example 3
Input
```
1
3 3
1 2
2 3
3 1
```
Expected output
```
1
```