Looping path P28620


Statement
 

pdf   zip

thehtml

Given a directed graph with n vertices and m arcs, and two vertices x and y, is there a path that goes from x to y, passing through at least some other vertex at least twice? We will call this a looping path. Note that it can visit x and y only once (at the beginning and at the end).

Input

Input consists of several cases, each with n and m, followed by m pairs u v, with uv, indicating an arc from u to v, followed by x and y, with xy. Assume 2 ≤ n ≤ 105, 0 ≤ m ≤ 5n, that vertices are numbered from 0 to n−1, and that there are no repeated arcs.

Output

For every graph, print “YES” if there is a looping path from x to y, and “NO” otherwise.

Public test cases
  • Input

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

    Output

    NO
    NO
    YES
    YES
    
  • Information
    Author
    Ángel García and Enrique Jiménez
    Language
    English
    Official solutions
    C++
    User solutions
    C++