1771. How Many Junctions Have an Odd Count
An UNDIRECTED graph has n vertices and m edges. The DEGREE of a vertex is
the number of edge-ends attached to it. Print how many vertices have an ODD
degree.
1-2, 2-3 -> 2 degrees 1, 2, 1
1-2, 2-3, 3-1 -> 0 degrees 2, 2, 2
1-1 -> 0 a self-loop gives vertex 1 degree 2
1-2, 1-2 -> 0 two parallel edges give each end degree 2
## The two conventions that decide the whole answer
``` a SELF-LOOP adds TWO to its vertex, not one. Both of its ends are attached there, and a walk that uses it arrives and departs along it. So a self-loop can never change a parity.
a PARALLEL EDGE adds one each time it is listed. Two copies of 1-2 give vertex 1 degree 2 and vertex 2 degree 2, so the pair of them changes no parity either, although one copy on its own changes both. ```
## What most people try first
Counting adj[v].length after building an adjacency list that skips the second
copy of a self-loop. That is the single commonest way to get this wrong, and
the third example is the test for it: a graph whose only edge is 1-1 has no
odd vertex, and a solution adding one for a self-loop reports 1.
The symptom is worth knowing because of what comes next. The answer to this question is always EVEN, so an odd answer is a bug and not an input.
## Why the answer is always even
Add up every degree. Each edge contributes exactly 2 to the total, one for each end, and a self-loop contributes 2 as well because both its ends sit on the same vertex. So
deg(1) + deg(2) + ... + deg(n) = 2 * m
which is even. A sum of integers is even only if an even number of them are odd. So the count of odd-degree vertices is even, always, whatever the graph. That identity is called the handshake lemma, and this problem's oracle asserts both halves of it on every input it checks.
## Why this number is worth computing
It is the quantity the Euler conditions are stated in. Problem 1772 shows that a connected graph can be drawn in ONE continuous stroke using every edge exactly once precisely when this count is 0 or 2, problem 1777 turns it into the fewest strokes needed when it is larger, and problem 1778 asks how many edges to add to bring it to 0. All three depend on getting self-loops and parallel edges right here first.
## Cost
O(n + m) time and O(n + m) space: one pass over the edges adding 1 to each
end, then one pass over the vertices testing the parity. No search and no
sorting. The answer is at most n, which is 200000, so nothing here comes
near the 2147483647 a signed 32-bit integer holds.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` may equal `v`, so self-loops can occur, and a self-loop adds 2 to its vertex - the same pair may be listed more than once, so parallel edges can occur - the graph may be disconnected
Input
The first line contains two integers n and m, the number of vertices and the number of edges.
Each of the next m lines contains two integers u and v, an undirected edge joining u and v.
Output
Print one integer, the number of vertices whose degree is odd.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.