Minimal Strokes for Drawing a Graph

Einstein has taken up painting, but he is rather lazy. He wishes to draw a picture of a graph using the minimum number of strokes (pen lifts). Given an undirected graph with \( n \) vertices (labeled from 1 to \( n \)) and \( m \) edges, determine the minimum number of strokes required to cover all edges without retracing any edge.

A stroke is defined as drawing a sequence of connected edges in one continuous line (without lifting the pen). For a connected component, an Eulerian trail exists if and only if the number of vertices with odd degree is either 0 or 2. In general, for each connected component that contains at least one edge, let \( o \) be the number of vertices with an odd degree. Then the minimum number of strokes needed for that component is given by:

[ S = \begin{cases} 1, & \text{if } o = 0, \ \frac{o}{2}, & \text{if } o > 0. \end{cases} ]

The answer is the sum of the strokes required over all connected components with edges.

inputFormat

The input starts with two integers \( n \) and \( m \) (the number of vertices and edges, respectively). The next \( m \) lines each contain two integers \( u \) and \( v \), indicating that there is an undirected edge between vertices \( u \) and \( v \).

Constraints:

• \(1 \le n \le 10^5\)
• \(0 \le m \le 10^5\)
• \(1 \le u, v \le n\) and \(u \neq v\)

outputFormat

Output a single integer, which is the minimum number of strokes required to draw all the edges of the graph.

sample

3 3
1 2
2 3
3 1

1