Is this a DFS traversal? P52199


Statement
 

pdf   zip

html

You are given an undirected graph with n vertices (numbered from 0) and m edges, and a sequence of k vertices. Can the sequence be the result of a Depth First Search traversal of the graph starting at 0? Please remember that a DFS explores as far as possible along each branch, and backtracks only when the current vertex has already been explored. The neighbours of each vertex can be visited in any order.

Input

Input consists of several cases, each one with n and m, followed by the m edges x y, followed by k, followed by k different vertices between 0 and n−1. Assume 1 ≤ n ≤ 104, 0 ≤ m ≤ 5n, x ≠ y, that there are no repeated edges, and 1 ≤ k ≤ n.

Output

For every case, print the right answer “yes” or “no”.

Public test cases

  • Input

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

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

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

    Output

    yes
no
yes
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++