Painting vertices P76043


Statement
 

pdf   zip

html

You are given a directed graph, where some vertices are initially painted and some are not, and two vertices x and y. Please paint the minimum number of additional vertices so that there is a path from x to y that only passes through painted vertices.

Input

Input consists of several cases. Every case begins with the number of vertices n, the starting vertex x and the final vertex y. Next comes a number m, followed by m different arcs u v where uv. Follow a number p, followed by the p vertices initially painted. Assume 2 ≤ n ≤ 104, xy, 0 ≤ m ≤ 5n, and 0 ≤ pn. The vertices are numbered starting at 0.

Output

For every case, print the minimum number of vertices to paint so that there is a path from x to y that only passes through painted vertices, x and y included. If it is impossible, state so.

Public test cases
  • Input

    2 1 0
    1  1 0
    0
    
    2 0 1
    0
    2  0 1
    
    5 0 2
    6  0 1  1 2  0 3  3 1  3 4  4 2
    4  0 3 4 2
    
    8 7 0
    11  4 1  6 0  7 4  5 3  7 5
    1 6  6 7  0 2  5 1  4 2  3 6
    3  6 4 2
    

    Output

    2
    impossible
    0
    3
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Semifinal
    Date
    2012-06-30