1778. The Fewest Edges To Add

An UNDIRECTED graph has n vertices and m edges, and ALL of its edges lie in one connected piece. Vertices with no edges at all may exist and are irrelevant.

Problem 1772 says a closed stroke covering every edge exists exactly when no vertex has an odd degree. Print the fewest NEW edges that have to be added so that such a closed stroke exists.

New edges may join any two vertices, including a pair already joined, so adding a second copy of an existing edge is allowed. A new self-loop is allowed too and is never useful.

1-2, 2-3, 3-1 -> 0 already closed 1-2, 2-3 -> 1 add 1-3, or a second copy of 1-2 1-2, 2-3, 2-4, 2-5 -> 2 four odd vertices 1-2, 1-3, 1-4, 1-5, 1-6 -> 3 degrees 5, 1, 1, 1, 1, 1: six odd

## The rule

answer = (number of odd-degree vertices) / 2

and that count is always even, by the handshake lemma of problem 1771, so the division is exact.

## What most people try first

Adding one edge per odd vertex. That gives odd rather than odd / 2, and it double-counts: a single new edge fixes TWO odd vertices at once, one at each end. On a path of three vertices, the answer is 1 and this rule says 2.

Adding `odd / 2` only when `odd > 2`, on the grounds that two odd vertices are already fine. They are fine for an OPEN stroke, which is problem 1772's PATH verdict. This problem wants a CLOSED one, so two odd vertices still cost one edge. The second example above is the test for that confusion, and it is the difference between this problem and the variant that asks for an open stroke, whose answer is max(0, odd / 2 - 1).

Worrying about connectivity. The constraints promise all the edges are in one piece, and a new edge between two vertices of that piece keeps it so. Note this is a real restriction and not a convenience: on two separate triangles the parity count is 0 and the true answer is 2, because the pieces have to be joined. That is a harder problem and it is not this one.

## Why odd / 2 is right

Lower bound: each new edge raises exactly two degrees by 1 each, or one degree by 2 if it is a self-loop. A self-loop changes no parity. So each new edge fixes at most two odd vertices, and odd / 2 edges are needed at minimum.

Upper bound: pair the odd vertices up arbitrarily and add one edge per pair. Each such edge flips the parity at both of its ends, so after odd / 2 additions every degree is even. The graph is still connected, because new edges only ever add routes. So problem 1772 gives a closed stroke.

A pair that is already joined gets a second parallel edge, which is explicitly allowed, so the construction never runs out of pairs to use.

## Cost

O(n + m): one pass over the edges for the degrees, one pass over the vertices counting the odd ones. No search is needed at all, because connectivity is promised. The answer is at most n / 2, so 100000, far below the 2147483647 a signed 32-bit integer holds.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - ALL of the edges lie in one connected piece, which is promised and not something to check - vertices with no edges at all may exist, and they never need anything added - self-loops can occur and add 2 to their vertex, so they never change a parity - parallel edges can occur, and a new edge may duplicate an existing one