1776. Print the One-Way Journey

A DIRECTED graph has n vertices and m arcs. Print the journey that traverses every arc exactly once in its own direction, as the sequence of m + 1 vertices visited. Print -1 if no such journey exists, and None when m is 0.

Problem 1775 does this for undirected edges. The algorithm is the same shape and TWO things change: the start rule, and the fact that an arc can only be taken forwards.

## The procedure, pinned, because the journey is not unique

``` build, for each vertex, the list of its OUTGOING arcs sorted by (the destination, then the arc's position in the input)

start = the vertex problem 1774 computes: if some vertex has one more arc out than in, that vertex otherwise the smallest vertex with at least one arc out

stack = [start]; walk = [] while the stack is not empty: x = top of stack if x has no unused outgoing arc: append x to walk; pop the stack else: take the FIRST unused arc out of x and push its destination reverse walk and print it ```

1->2, 2->3, 3->1 -> 1 2 3 1 1->2, 2->3 -> 1 2 3 1->2, 2->1, 1->3, 3->1 -> 1 2 1 3 1 1->1 -> 1 1 1->2, 1->3 -> -1

## Why no "used" flag per arc is needed here, unlike 1775

An undirected edge sits in TWO incidence lists, so using it from one end has to be visible from the other, which is why problem 1775 needs a per-edge boolean. A directed arc sits in ONE list, the list of its tail. So advancing that list's pointer past the arc is all the marking required, and the pointer never moves backwards.

That is the whole difference in the data structure, and it is also why the directed version is the easier one to write and the one usually seen first.

## What most people try first

Reusing the undirected start rule. On 1->2, 2->3 the undirected rule looks at degrees, finds vertices 1 and 3 odd, and picks 1, which happens to be right. On 2->3, 3->4, 4->2, 2->5 the undirected degrees are 1 at vertex 5, 3 at vertex 2 and 2 elsewhere, so the undirected rule starts at vertex 2; the directed rule also starts at 2 because its outdegree exceeds its indegree. The rules agree often enough to pass small tests and are not the same rule. On 1->2, 2->1, 2->3, 3->2 every undirected degree is even and so is every directed difference, so both say "closed, start anywhere with an edge" and both give 1. The input that separates them is 1->2, 1->2, 3->1, 4->1, where the undirected degrees are all even and the directed answer is -1.

Starting at the smallest vertex when a surplus vertex exists. The journey MUST begin at the vertex with one more arc out than in. Beginning anywhere else leaves that vertex with an outgoing arc nothing can ever return to use, and the stack-based search then returns a sequence that is not a journey at all. It still returns something, which is why this problem's oracle verifies the result structurally rather than trusting the start rule.

Recursion. The depth is the number of arcs, so 200000 arcs overflow the Python recursion limit and the default stack in C, C++ and Java.

## Cost

O(n + m log m) for the sort and O(n + m) for the journey.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - the arcs are DIRECTED and may only be traversed from `u` to `v` - self-loops can occur and are used once like any other arc - parallel arcs can occur, and the earlier-listed copy is taken first - the graph may be disconnected, and vertices with no arcs never prevent a journey - the journey is not unique, so the procedure in the statement fixes which one to print