Euler: Count Odd-Degree Vertices

Euler: count the odd-degree vertices

The key quantity for "can it be drawn in one stroke" is the number of odd-degree vertices. Read an undirected graph and print how many vertices have an odd degree.

Complete it: add 1 to both endpoints' degree for each edge, then count those with an odd degree.

Hint: an undirected edge u–v does deg[u]++ and deg[v]++. A vertex with deg[i] % 2 == 1 is odd. Fact: by the handshake lemma, the count of odd-degree vertices is always even (0, 2, 4, ...).

Input

• Line 1: V E (vertices, edges).
• Next E lines: u v, an undirected edge (E may be 0).

Output

• One line: the number of odd-degree vertices.

Example: input 4 3 / 0 1 / 1 2 / 2 3 -> 2 (vertices 0 and 3 have degree 1; 1 and 2 have degree 2).