Problem I
Mårtens DFS

Du får givet en enkel, sammanhängande graf $G$ med $N$ hörn. Varje hörn i $G$ har numrerats med tal mellan $0$ och $N-1$.

Avgör om en lista med heltal $L$ är en giltig djupet först-sökning. En giltig djupet först-sökning är en som kan genereras av följande procedur, anropad med något argument mellan $0$ och $N - 1$:

DFS(start):
  skriv ut start
  sett[start] = true
  för varje v : grannar(start):
    om inte sett[start]:
      DFS(v)

Observera att grannarna till ett visst hörn kan gås igenom i vilken ordning som helst av Mårtens algoritm.

Indata

Den första raden innehåller två heltal $1 \le N \le 100\, 000$ och $0 \le E \le 300\, 000$, antalet hörn och kanter i $G$.

De nästa $E$ raderna innehåller två heltal $0 \le a, b \le N - 1$, som beskriver en kant i $G$ mellan hörnen $a$ och $b$.

Den sista raden kommer innehålla en (möjligtvis tom) blankstegs-separerad lista $L$ med heltal.

Utdata

Du ska skriva ut YES om $L$ är en giltig djupet först-sökning. Annars ska du skriva ut NO.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

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