Adding Edges

Given an undirected graph, add as few edges as possible so that the resulting graph is connected and has an Euler trail.

An Euler trail is a path that uses every edge exactly once. The starting vertex and ending vertex may be the same or different.

The first line contains the number of vertices V and the number of edges E.

2 <= V <= 1,000
1 <= E <= V * (V - 1) / 2

The vertices are numbered from 1 to V. Each of the next E lines contains two distinct vertices a and b that form an edge. All edges in the input are distinct.

Print the minimum number of edges that must be added.