Is this a DFS traversal?

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 \le n \le 10^4$ , $0 \le m \le 5n$ , $x \ne y$ , that there are no repeated edges, and $1 \le k \le n$ .

Output

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

Problem information

Author: Salvador Roura

Generation: 2026-01-25T11:09:27.030Z