Cycles P36563

Given a directed graph with $n$ vertices and $m$ arcs, can you keep exactly $n$ arcs (and remove the rest) in such a way that every vertex belongs to one cycle of the resulting graph?

Input

Input consists of several cases, each one with $n$ and $m$, followed by $n$ pairs $x$ $y$ to indicate an arc from $x$ to $y$, with $x \ne y$. Assume $2 \le n \le 1000$, $n \le m \le 5n$, that vertices are numbered from 0 to $n-1$, and that there are no repeated arcs.

Output

Print one line for every given graph. If there is no solution, print “no”. Otherwise, print “yes” followed by the $n$ chosen arcs in any order. If there is more than one solution, you can print any one. Follow strictly the format of the sample output.

Hint

Consider the max-flow problem.