We’re preparing your current view and syncing the latest data.
You are given an undirected graph with n nodes and a list of edges. Your task is to add as few edges as possible to the graph to make the degree of every node even. You may add any edges between any two nodes, including edges that already exist, as long as the resulting degree of every node is even.
The input includes an integer n, the number of nodes, and a list of edges where each edge is represented as a pair of nodes [u, v]. Nodes are numbered from 1 to n.
Return the minimum number of edges that need to be added to make all node degrees even.
1 <= n <= 10^5, 0 <= number of edges <= 10^5, 1 <= edges[i][0], edges[i][1] <= n
Example 1
Input
n = 4, edges = [[1,2],[2,3],[3,4]]
Output
1
Explanation
Adding an edge between node 1 and node 4 makes all degrees even.
Example 2
Input
n = 3, edges = [[1,2],[2,3],[3,1]]
Output
0
Explanation
Every node already has an even degree.