Eulerian cycle

Definition

1. A eulerian cycle is an ordinary cycle in a directed or undirected graph that contains each edge/arc exactly once.
2. A directed or undirected graph is called eulerian if it admits a eulerian cycle.

Remark: It is easy to see (and follows from the classical algorithm) that a graph [math]\displaystyle{ G }[/math] is eulerian if, and only if:

1. Undirected case: [math]\displaystyle{ G }[/math] is connected, and each node has even degree.
2. Directed case: [math]\displaystyle{ G }[/math] is strongly connected, and for each node [math]\displaystyle{ v }[/math], the in degree of [math]\displaystyle{ v }[/math] equals the out degree of [math]\displaystyle{ v }[/math].

Input

A strongly connected directed or connected undirected graph.

Output

A eulerian cycle as an alternating sequence of nodes and edges/arcs or, alternatively, the (correct) message that no such cycle exists.

Known algorithms

Classical eulerian cycle algorithm