Toll
Time limit1sMemory limit128 MB
Each selected town must charge on exactly one incident road, and no road may be charged by both endpoints. Maximize selected towns in a general graph, not necessarily the whole graph.
Problem
The kingdom of Byteotia has towns joined by two-way roads. Every road directly connects two different towns, and no pair of towns is joined by more than one road (a road may still run through a tunnel or over a flyover).
Each town would like to collect a toll from travellers, but to keep the merchants happy the king restricts this privilege with two rules:
- A town that collects toll does so on exactly one of the roads that touch it, no matter which way a traveller uses that road.
- On any single road at most one of its two endpoint towns may collect toll; the two endpoints can never both charge the same road.
Because of these rules some towns can be left with no road to charge. Your task is to find the largest number of towns that can collect toll at the same time.
Write a program that:
- reads the description of Byteotia's road network from standard input,
- computes the maximum number of towns that can collect toll,
- writes that number to standard output.
Input
The first line contains two integers and (, ): the number of towns and the number of roads. Towns are numbered from to . Each of the next lines contains two integers and (), meaning that towns and are directly connected by a road.
Output
Print one integer: the maximum number of towns that can collect toll while obeying the rules above.
Hint

In the picture an arrow points from a road to the town that collects toll on it. Every town is served by exactly one road, and no road is charged by both of its endpoints; the road between towns and collects no toll at all. In this network all four towns manage to collect toll, so the answer is .