1773. Where Must the Pen Start
An UNDIRECTED graph has n vertices and m edges. Problem 1772 says WHETHER
every edge can be traced exactly once without lifting the pen. This says where
the pen has to start.
Print the SMALLEST vertex from which such a trace exists. Print -1 if no trace
exists at all, and 0 when m is 0, since then the trace is empty and starts
nowhere.
1-2, 2-3 -> 1 the two ends are 1 and 3; the smaller is 1
2-3, 3-4 -> 2
1-2, 2-3, 3-1 -> 1 closed, so any vertex works; the smallest is 1
4-5, 5-6, 6-4 -> 4 closed, but vertices 1 to 3 have no edges
1-2, 3-4 -> -1
## The rule, and the trap inside it
odd == 0 -> the trace closes, so EVERY vertex that has an edge works, and the
answer is the smallest vertex with a non-zero degree.
odd == 2 -> the trace is open and must start at an endpoint, which must be an
ODD vertex. The answer is the smaller of the two.
otherwise -> -1
The trap is the first line. "Any vertex works" is false as stated: a vertex with NO edges does not work, because the pen would have to jump to reach the edges. So the answer in the closed case is the smallest vertex of non-zero degree, not vertex 1. The fourth example above is the test for it, where the answer is 4 and a solution printing 1 looks right on every graph whose vertex 1 happens to be used.
## Why an open trace must start at an odd vertex
Problem 1772 proves the parity statement: in an open trace the only odd-degree vertices are the two endpoints. So the start is one of them, and both really do work, because reversing a trace gives a trace. With exactly two odd vertices, the smaller one is the answer.
## What most people try first
Printing the first odd vertex without checking a trace exists at all. On
1-2, 2-3, 2-4, 2-5 the first odd vertex is 1 and the answer is -1: four odd
vertices mean no trace, so there is no start to report. The existence test comes
first.
The second mistake is printing the first odd vertex found during the degree scan rather than the smallest. Those coincide only if the scan runs upwards, which is easy to get wrong when the odd vertices are collected into a list during a depth-first search instead.
## Cost
O(n + m): one pass for the degrees, one search for the connectivity of the
edge-bearing vertices, one upward scan for the smallest qualifying vertex. The
search is ITERATIVE, since a path of 200000 vertices is permitted and recursion
on it overflows Python's recursion limit and the default stack elsewhere.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - self-loops can occur and add 2 to their vertex, so they never change a parity - parallel edges can occur - the graph may be disconnected, and vertices with no edges never prevent a trace
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v, an undirected edge joining u and v.
Output
Print one integer: the smallest vertex from which the whole graph can be traced using every edge exactly once, or -1 if no such trace exists, or 0 when m is 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.