Minimal Road Repairs for Eulerian Trail

In a network of cities connected by roads, some roads may be poorly maintained and require repairs. The goal is to determine the minimal number of additional road repairs needed so that the road network supports an Eulerian trail. Recall that an undirected graph has an Eulerian trail if and only if it is connected and it has either 0 or 2 vertices of odd degree. In this problem, if the graph is connected and all vertices have even degree, no repair is needed. If exactly two vertices have odd degree, one repair is required; otherwise, if there are (k) (with (k \ge 4)) vertices of odd degree, the minimum number of road repairs needed is given by the formula [ \text{repairs} = \frac{k - 2}{2}, ] where (k) is the total number of vertices with odd degree. If the graph is disconnected, it is impossible to have an Eulerian trail, and you should output -1.

inputFormat

The first line contains two integers (n) and (m) ((1 \leq n \leq 10^5), (0 \leq m \leq 10^5)), representing the number of cities and the number of roads. The following (m) lines each contain two integers (u) and (v) ((1 \leq u, v \leq n)), representing an undirected road between cities (u) and (v).

outputFormat

Print a single integer: the minimal number of roads that need to be repaired so that the network has an Eulerian trail. If it is impossible because the graph is disconnected, output -1.## sample

3 3
1 2
2 3
3 1

0