# Problem G

Eulerian Graphs

The seven bridges connected four different pieces of land, all separated by rivers. The question was whether it was possible to walk over all the bridges in a tour exactly once. Euler solved the problem by proving that no such walk was possible.

The problem can be generalized using graphs, where we ask if there is any walk in a connected graph that passes each edge exactly once. Euler realized that this is the case exactly when all vertices have even degree, possibly except for two (which must then be the first and last vertices of the walk).

A generalization of Euler’s result is for *directed*
graphs, where an edge may be walked only in the direction it is
pointing. Euler’s rule is simple to adapt to the directed case.
A graph has such a walk exactly when the number of incoming and
outgoing edges for each vertex are equal, except that one
vertex may have one more outgoing edge than incoming edges, and
one vertex can have one more incoming than outgoing edge. The
walk must then start and end at those vertices, respectively.
Furthermore, the graph must be connected if the edges were
undirected^{1}.

Given all the edges in a directed graph (which is connected if its edges were undirected), determine if it has a walk that passes each edge exactly once. Also, determine if the walk can start anywhere or if there are specific vertices where the walk must start and end.

## Input

The first line contains integers $N$ ($2 \le N \le 100\, 000$), the number of vertices, and $M$ ($0 \le M \le 1\, 000\, 000$), the number of edges. This is followed by $M$ lines, one for each edge $a \rightarrow b$, containing the numbers $a$ and $b$ ($1 \le a, b \le N$).

## Output

Output `no` if there is no such
walk, `anywhere` if there is a walk
that may start anywhere, or the numbers of the start and end
vertices if there is a walk that must start and end at two
specific vertices.

Sample Input 1 | Sample Output 1 |
---|---|

2 1 1 2 |
1 2 |

Sample Input 2 | Sample Output 2 |
---|---|

2 2 1 2 1 2 |
no |

Sample Input 3 | Sample Output 3 |
---|---|

2 4 1 2 2 1 1 1 2 2 |
anywhere |

**Footnotes**

- Except if there are isolated vertices (those without neighbors), which we disregard in this problem.