Problem G
Eulerian Graphs

Leonhard Euler

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¹.

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.

2 1
1 2

1 2

2 2
1 2
1 2

no

2 4
1 2
2 1
1 1
2 2

anywhere