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 ≠ y. Assume 2 ≤ n ≤ 1000, n ≤ m ≤ 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.

Public test cases

**Input**

3 3 0 1 1 2 2 0 3 4 0 1 1 2 2 1 1 0 4 6 0 2 2 1 1 3 3 0 2 0 3 1 4 6 0 2 2 1 1 3 3 0 2 0 3 1

**Output**

yes 0 1 1 2 2 0 no yes 0 2 1 3 2 1 3 0 yes 2 0 3 1 1 3 0 2

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++