A conflict graph has n people (numbered 0 to n-1) and m undirected rivalry edges. You want to split people into two rooms so that no rivalry is inside a single room. A connected component can be split this way exactly when it is bipartite (2-colorable). A component fails when it contains a cycle of odd length.
Count how many connected components are not bipartite.
Input format
Line 1: two integers n and m.
Next m lines: two integers u v (0-indexed) — a rivalry between u and v.
The graph is undirected. A self-loop (u == v) makes its component non-bipartite. Duplicate edges may appear.
Output format
A single integer: the number of connected components that are not bipartite.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ m ≤ 200000
- 0 ≤ u, v ≤ n-1
An isolated vertex forms a bipartite component (it contributes 0 to the answer).