A street sweeper wants a round that covers every street and returns to the depot. That is an Eulerian cycle, which needs every node to have even degree. Where the degrees are odd the sweeper must add duplicate stretches: each added edge fixes the parity of its two endpoints, so the odd nodes can be paired off.
Write edges_to_eulerise(n, edges) returning the smallest number of edges to add, or -1 when the edges do not all lie in one connected piece.
Examples
Input: n = 3, edges = [(0, 1), (1, 2)]
Output: 1
Explanation: 0 and 2 are odd; one edge between them closes the round.
Input: n = 4, edges = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
Output: 2
Explanation: all four nodes have degree 3, so two added edges pair them up.
Constraints
1 <= n <= 10**5,0 <= len(edges) <= 2 * 10**5- Added edges may duplicate an existing one, and isolated nodes are ignored.
Goals
- Pair up the odd-degree nodes to make every degree even
- See why the answer is half their number and never less
- Refuse the job when the graph is in pieces