1772. Can the Whole Thing Be Traced Without Lifting the Pen

An UNDIRECTED graph has n vertices and m edges. You want to trace every edge exactly once without lifting the pen. Print

CIRCUIT if that is possible AND the trace can end where it began PATH if it is possible but only by starting and ending at different places NONE if it is not possible at all

A graph with no edges at all counts as CIRCUIT: the empty trace uses every one of its zero edges and ends where it started.

1-2, 2-3, 3-1 -> CIRCUIT 1-2, 2-3 -> PATH 1-2, 3-4 -> NONE two pieces, the pen would have to jump 1-2, 2-3, 2-4, 2-5 -> NONE four odd vertices 1-1 -> CIRCUIT a self-loop is traced and returns

## The condition, stated for the UNDIRECTED case only

NONE unless every edge lies in ONE connected piece then, with odd = the number of odd-degree vertices (problem 1771): odd == 0 -> CIRCUIT odd == 2 -> PATH otherwise -> NONE

Vertices with NO edges are ignored for the connectivity test. A graph of five isolated vertices and one edge between two of them is PATH, not NONE: the pen never has to visit the other three.

Problem 1774 gives the DIRECTED condition, which is a different statement and not this one with arrows added.

## What most people try first

Checking the parities and forgetting connectivity. 1-2, 3-4 has four odd vertices so it fails anyway, but 1-2, 2-1, 3-4, 4-3 has no odd vertex at all and is still NONE, because it is two separate loops. That input is the test for this mistake.

The opposite omission is checking connectivity and forgetting the isolated vertices. A graph with n = 5 and the single edge 1-2 is connected in the sense that matters and disconnected in the sense of "every vertex reachable from vertex 1". Testing the wrong one reports NONE.

## Why the parity condition is necessary

Walk the trace and count, at each vertex, how many of its edge-ends the trace uses. Every time the trace passes THROUGH a vertex it uses two: one to arrive, one to leave. The only exceptions are the two ends of the trace, which use one extra each, and if the trace is closed those two coincide and contribute two more to the same vertex.

Since the trace uses every edge-end exactly once, a vertex's degree is twice its number of pass-throughs, plus one if the trace starts there and one if it ends there. So:

closed trace -> every degree is even open trace -> exactly two degrees are odd, the two endpoints

No other count is possible. An odd count of odd vertices cannot even arise, by the handshake lemma of problem 1771.

## Why it is sufficient

That direction is Hierholzer's argument and problem 1775 builds the trace itself. In outline: walk anywhere without repeating an edge until stuck. With every degree even you can only get stuck where you started, so you have a closed loop. If edges remain, some vertex on your loop still has unused edges, since the graph is connected; start a second closed loop there and splice it into the first. Repeat. Every splice uses more edges and the process ends with all of them used. For the odd == 2 case, add a temporary edge between the two odd vertices, find the circuit, then delete the temporary edge from it.

## Cost

O(n + m) for the degrees and one search for the connectivity, so O(n + m) overall. The search must be ITERATIVE: a path of 200000 vertices is permitted and recursion on it overflows Python's recursion limit and the default stack in C, C++ and Java.

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, and vertices with no edges never prevent a trace