Cactus of Vanya#3275
Few programmers are unaware of the legendary ability of cacti to absorb radiation! Programmer Vanya is a firm believer in this property, so a massive cactus stands beside his large 19-inch CRT monitor. This cactus has a unique structure: it can be represented as a connected undirected multigraph where each edge belongs to at most one simple cycle. On New Year's Eve, Vanya decided to adorn his cactus with a string of lights. The bulbs of this garland can only be placed at the vertices of the cactus, and a bulb placed at a vertex illuminates all edges incident to that vertex.
Vanya wants to ensure that every edge of his cherished cactus is illuminated. What is the minimum number of bulbs he needs if he places them optimally?
The first line of the input file contains two numbers: 2 N 100000, the number of vertices in the cactus, and M, the number of edges.
The following M lines provide descriptions of the edges. Each edge is described by two numbers separated by a space: 1 a, b N, a \neq b, indicating the vertices it connects.
Output a single number—the answer to the problem.
Example 1