Problem I
Mårten's DFS

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.

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

YES

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

YES

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

NO

4 3
0 1
1 2
2 3
0 1 2

NO

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

NO