Hide

Problem I
Mårten's DFS

Languages en sv

You will be given a simple, connected graph $G$ with $N$ vertices. Each vertex in $G$ has been numbered between $0$ and $N - 1$.

Determine if a list $L$ is a valid depth first-search order. A valid depth first-search order is one that can be generated by the following procedure, called with some argument between $0$ and $N - 1$:

DFS(start):
  print start
  seen[start] = true
  for each v : neighbours(start):
    if not seen[v]:
      DFS(v)

Note that the neighbours to the vertex $v$ can be iterated through in any order by Mårten’s algorithm.

Input

The first line of input contains two integers $1 \le N \le 100\, 000$ and $0 \le E \le 300\, 000$, the number of vertices and edges of $G$.

The next $E$ lines contains two integers $0 \le a, b \le N - 1$, describing an edge in $G$ between the vertices $a$ and $b$.

The final line will contain a space-separated list $L$ of (possible none) integers.

Output

You should output YES if $L$ is a valid depth first-search order. Otherwise, you should output NO.

Grading

Your solution will be graded on a number of subtasks. To get the points for a subtask, you must be accepted on all test cases in the subtask.

Subtask

Points

Limits

$1$

$19$

$1 \le N \le 8$, $1 \le E \le 28$

$2$

$43$

$1 \le N \le 1\, 000$, $1 \le E \le 5\, 000$

$3$

$38$

No additional constraints.

Sample Input 1 Sample Output 1
4 3
0 1
1 2
2 3
0 1 2 3
YES
Sample Input 2 Sample Output 2
4 3
0 1
1 2
2 3
2 1 0 3
YES
Sample Input 3 Sample Output 3
4 3
0 1
1 2
2 3
2 1 3 0
NO
Sample Input 4 Sample Output 4
4 3
0 1
1 2
2 3
0 1 2
NO
Sample Input 5 Sample Output 5
4 3
0 1
1 2
2 3
1 0 4 3 2
NO

Please log in to submit a solution to this problem

Log in