Cycles P36563


Statement
 

pdf   zip

thehtml

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 xy. Assume 2 ≤ n ≤ 1000, nm ≤ 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++